2018-team4-modules-点分治

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
// 点分治求树上路径边权和为3的倍数的路径的数目
struct Edge{
    int to,next,dis;
}G[maxn<<1];
int head[maxn],cnt;
void add(int u,int v,int d){
    G[++cnt].to = v;
    G[cnt].next = head[u];
    G[cnt].dis = d;
    head[u] = cnt;
}
bool vis[maxn];
int dis[maxn],root,f[maxn];
int size,siz[maxn];
#define v G[i].to
void dfs1(int u,int fa){
    siz[u] = 1;f[u] = 0;
    for(int i = head[u];i;i=G[i].next){
        if(v == fa || vis[v]) continue;
        dfs1(v,u);
        siz[u] += siz[v];
        f[u] = max(f[u],siz[v]);
    }
    f[u] = max(size - siz[u],f[u]);
    if(f[u] < f[root]) root = u;
}
int num[5];
void dfs2(int u,int fa){
    ++num[dis[u]];siz[u] = 1;
    for(int i = head[u];i;i=G[i].next){
        if(v == fa || vis[v]) continue;
        dis[v] = dis[u] + G[i].dis;
        dis[v] %= 3;
        dfs2(v,u);
        siz[u] += siz[v];
    }return;
}
int calc(int u,int k){
    num[0] = num[1] = num[2] = 0;
    dis[u] = k % 3;
    dfs2(u,0);
    return num[1]*num[2]*2 + num[0]*num[0];
}
int ans = 0;
void dfs(int u){
    ans += calc(u,0);
    vis[u] = true;
    for(int i = head[u];i;i=G[i].next){
        if(vis[v]) continue;
        ans -= calc(v,G[i].dis);
        size = siz[v];root = 0;
        dfs1(v,0);
        dfs(root);
    }
}
#undef v
int main(){
    int n;read(n);
    for(int i=1,u,v,d;i<n;++i){
        read(u);read(v);read(d);
        add(u,v,d);add(v,u,d);
    }
    size = f[0] = n;
    dfs1(1,0);
    dfs(root);
    return 0;
}
}}}

// 点分治求树上路径边权和为3的倍数的路径的数目
struct Edge{
    int to,next,dis;
}G[maxn<<1];
int head[maxn],cnt;
void add(int u,int v,int d){
    G[++cnt].to = v;
    G[cnt].next = head[u];
    G[cnt].dis = d;
    head[u] = cnt;
}
bool vis[maxn];
int dis[maxn],root,f[maxn];
int size,siz[maxn];
#define v G[i].to
void dfs1(int u,int fa){
    siz[u] = 1;f[u] = 0;
    for(int i = head[u];i;i=G[i].next){
        if(v == fa || vis[v]) continue;
        dfs1(v,u);
        siz[u] += siz[v];
        f[u] = max(f[u],siz[v]);
    }
    f[u] = max(size - siz[u],f[u]);
    if(f[u] < f[root]) root = u;
}
int num[5];
void dfs2(int u,int fa){
    ++num[dis[u]];siz[u] = 1;
    for(int i = head[u];i;i=G[i].next){
        if(v == fa || vis[v]) continue;
        dis[v] = dis[u] + G[i].dis;
        dis[v] %= 3;
        dfs2(v,u);
        siz[u] += siz[v];
    }return;
}
int calc(int u,int k){
    num[0] = num[1] = num[2] = 0;
    dis[u] = k % 3;
    dfs2(u,0);
    return num[1]*num[2]*2 + num[0]*num[0];
}
int ans = 0;
void dfs(int u){
    ans += calc(u,0);
    vis[u] = true;
    for(int i = head[u];i;i=G[i].next){
        if(vis[v]) continue;
        ans -= calc(v,G[i].dis);
        size = siz[v];root = 0;
        dfs1(v,0);
        dfs(root);
    }
}
#undef v
int main(){
    int n;read(n);
    for(int i=1,u,v,d;i<n;++i){
        read(u);read(v);read(d);
        add(u,v,d);add(v,u,d);
    }
    size = f[0] = n;
    dfs1(1,0);
    dfs(root);
    return 0;
}