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

[bzoj] 2152 聪聪可可 || 树分治

程序员文章站 2022-05-08 18:26:50
...

原题

给出一颗树,求有多少条路径满足路径上的权值和是3的倍数,输出答案比n的最简分数。


大概是树的点分治的模板题啊。
用重心把树分治,在“合并”的过程中求经过重心的权值和为3的倍数的路径条数。
calcg用bfs每次求出重心,calc用于处理每个点到当前根的距离。
ans每次先加上当前所在树的calc,再减去每一棵子树的calc(不然他们就被重复计算了)。

#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 20010
typedef long long ll;
using namespace std;
int n,cnt=1,sze[N],son[N],q[N],f[N],head[N];
ll dis[N],ans,cont[10];
bool vis[N];
struct hhh
{
    int w,to,next;
}edge[2*N];

int read()
{
    int ans=0,fu=1;
    char j=getchar();
    for (;(j<'0' || j>'9') && j!='-';j=getchar()) ;
    if (j=='-') j=getchar(),fu=-1;
    for (;j>='0' && j<='9';j=getchar()) ans*=10,ans+=j-'0';
    return ans*fu;
}

void add(int u,int v,int w)
{
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    edge[cnt].w=w;
    head[u]=cnt++;
}

ll gcd(ll x,ll y)
{
    return y?gcd(y,x%y):x;
}

int calcG(int x)
{
    int qn,u,v;
    q[qn=1]=x;
    f[x]=0;
    for (int ql=1;ql<=qn;ql++)
    {
    u=q[ql];
    sze[u]=1;
    son[u]=0;
    for (int i=head[u];i;i=edge[i].next)
        if (!vis[v=edge[i].to] && v!=f[u])
        q[++qn]=v,f[v]=u;
    }
    int ret,mn=0x3f3f3f3f;
    for (int ql=qn;ql>=1;ql--)
    {
    u=q[ql];
    sze[f[u]]+=sze[u];
    son[f[u]]=max(son[f[u]],sze[u]);
    son[u]=max(son[u],qn-sze[u]);
    if (son[u]<mn) ret=u,mn=son[u];
    }
    return ret;
}

ll calc(int x,int l)
{
    int qn,v,u;
    memset(cont,0,sizeof(cont));
    q[qn=1]=x;
    dis[x]=l%3;
    f[x]=0;
    for (int ql=1;ql<=qn;ql++)
    {
    u=q[ql];
    cont[dis[u]]++;
    for (int i=head[u];i;i=edge[i].next)
        if (!vis[v=edge[i].to] && v!=f[u])
        q[++qn]=v,f[v]=u,dis[v]=(dis[u]+edge[i].w)%3;
    }
    return cont[0]*cont[0]+cont[1]*cont[2]*2;
}

void solve(int x)
{
    int G=calcG(x);
    vis[G]=1;
    ans+=calc(G,0);
    for (int i=head[G];i;i=edge[i].next)
    if (!vis[edge[i].to]) ans-=calc(edge[i].to,edge[i].w);
    for (int i=head[G];i;i=edge[i].next)
    if (!vis[edge[i].to]) solve(edge[i].to);
}

int main()
{
    n=read();
    for (int i=1,u,v,w;i<n;i++)
    {
    u=read();v=read();w=read();
    add(u,v,w);
    add(v,u,w);
    }
    solve(1);
    ll g=gcd(ans,(ll)n*n);
    printf("%lld/%lld\n",ans/g,(ll)n*n/g);
    return 0;
}