欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【BZOJ 2152】聪聪可可 点分治

程序员文章站 2022-05-08 18:27:14
...

对于一棵树,fdrt找到重心,然后分治每个子树。

在一棵以重心为根的树上,符合条件的链是:

  1.过重心(根)

  2.不过重心

对于1我们只需dfs出距离重心(根)的距离然后统计再减去有重叠的边

对于2我们只需递归处理子树,这样2就分为过子树的根(重心)的链和不过子树根(重心)的链······

这就是点分治啦,貌似边分治更优,但是为了减少代码量,效率什么的我统统都不要(╬▔皿▔)

#include<cstdio>
#include<cstring>
#include<algorithm>
#define read(x) x=getint()
using namespace std;
const int N=20003;
inline const int max( const int &a, const int &b) {return a>b?a:b;}
inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }
struct node {
    int nxt, to, w;
} E[N<<1];
int point[N], size[N], ma[N], n, cnt=0, rt=0, ans=0, table[N], tn, di[N];
bool vis[N];
inline void insect( int x, int y, int z) {
    cnt++;
    E[cnt].nxt = point[x];
    E[cnt].to = y;
    E[cnt].w = z;
    point[x] = cnt;
}
inline void fdrt( int x, int fa, int s) {
    size[x] = 1;
    ma[x] = 0;
    for( int tmp = point[x]; tmp; tmp = E[tmp].nxt)
        if ( !vis[E[tmp].to] && E[tmp].to != fa) {
            fdrt( E[tmp].to, x, s);
            size[x] += size[E[tmp].to];
            ma[x] = max( ma[x], size[E[tmp].to]);
        }
    if ( s - ma[x] > ma[x])
        ma[x] = s - ma[x];
    if ( ma[x] < ma[rt])
        rt = x;
}
inline void mktb( int x, int fa) {
    table[ ++tn] = di[x];
    for( int tmp = point[x]; tmp; tmp = E[tmp].nxt)
        if ( !vis[E[tmp].to] && E[tmp].to != fa) {
            di[E[tmp].to] = di[x] + E[tmp].w;
            mktb( E[tmp].to, x);
        }
}
inline int work( int x, int beg) {
    int cn0 = 0, cn1 = 0, cn2 = 0;
    tn = 0;
    di[x] = beg;
    mktb( x, -1);
    for( int i = 1; i <= tn; ++i) {
        switch ( table[i] % 3) {
            case 0:
                ++cn0;
            break;
            case 1:
                ++cn1;
            break;
            case 2:
                ++cn2;
            break;
        }
    }
    return cn0 * cn0 + ( ( cn1 * cn2) << 1);
}
inline void dfs( int x, int s) {
    vis[x] = 1;
    ans += work( x, 0);
    for( int tmp = point[x], ss; tmp; tmp = E[tmp].nxt)
        if ( !vis[E[tmp].to]) {
            ans -= work( E[tmp].to, E[tmp].w);
            if ( size[E[tmp].to] > size[x])
                ss = s - size[x];
            else
                ss = size[E[tmp].to];
            rt = 0;
            fdrt( E[tmp].to, x, ss);
            dfs( rt, ss);
        }
}
inline int gcd( int x, int y) {
    int r = x % y;
    while ( r) {
        x = y;
        y = r;
        r = x % y;
    }
    return y;
}
int main() {
    read( n);
    int u, v, e;
    for( int i = 1; i < n; ++i) {
        read( u);
        read( v);
        read( e);
        e %= 3;
        insect( u, v, e);
        insect( v, u, e);
    }
    ma[0] = n+3;
    memset( vis, 0, sizeof(vis));
    fdrt( (n+1)>>1, -1, n);
    dfs( rt, n);
    int m = n * n, tong = gcd( ans, m);
    printf( "%d/%d\n", ans / tong, m / tong);
    return 0;
}

点分治完成啦,找重心估计s时偷了点懒效率立刻就低了∑(っ °Д °;)っ还是改回来了

还有我的码风这次有点奇怪⁄(⁄ ⁄•⁄ω⁄•⁄ ⁄)⁄.是不是不再像以前那么挤了ヾ (o ° ω ° O ) ノ゙