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

[点分治]BZOJ 2152——聪聪可可

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

题目描述

给出一棵有边权的树。

求边权和%3=0的路径数。

解题思路

累计以每个点为路径LCA的方案数,所以直接点分就好了。

累计方法为分别找出距离某个点路径和为0,1,2的方案数,返回2t[1]t[2]+t[0]t[0]

然后减去所以子树方案就是当前方案。

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=20005;
int tot,lnk[maxn],nxt[2*maxn],son[2*maxn],w[2*maxn];
int n,ro,t[5],s[maxn],sum,F[maxn],ans,d[maxn];
bool vis[maxn];
inline int _read(){
    int num=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') num=num*10+ch-48,ch=getchar();
    return num;
}
void add(int x,int y,int z){nxt[++tot]=lnk[x];lnk[x]=tot;son[tot]=y;w[tot]=z;}
int gcd(int x,int y){if (!y) return x;return gcd(y,x%y);}
void getro(int x,int fa){
    s[x]=1;F[x]=0;
    for (int j=lnk[x];j;j=nxt[j]) if (!vis[son[j]]&&son[j]!=fa){
        getro(son[j],x);
        s[x]+=s[son[j]];
        F[x]=max(F[x],s[son[j]]);
    }
    F[x]=max(F[x],sum-s[x]);
    if (F[x]<F[ro]) ro=x;
}
void DFS(int x,int fa){
    t[d[x]]++;
    for (int j=lnk[x];j;j=nxt[j]) if (!vis[son[j]]&&son[j]!=fa){
        d[son[j]]=(d[x]+w[j])%3;
        DFS(son[j],x);
    }
}
int cal(int x,int v){
    t[0]=t[1]=t[2]=0;d[x]=v;
    DFS(x,0);
    return t[1]*t[2]*2+t[0]*t[0];
}
void work(int x){
    ans+=cal(x,0);vis[x]=1;
    for (int j=lnk[x];j;j=nxt[j]) if (!vis[son[j]]){
        ans-=cal(son[j],w[j]%3);
        ro=0;sum=s[son[j]];
        getro(son[j],0);work(ro);
    }
}
int main(){
    freopen("exam.in","r",stdin);
    freopen("exam.out","w",stdout);
    n=_read();F[0]=n;
    for (int i=1;i<n;i++){
        int x=_read(),y=_read(),z=_read();
        add(x,y,z);add(y,x,z);
    }
    sum=n;getro(1,0);work(ro);
    int k=gcd(ans,n*n);
    printf("%d/%d\n",ans/k,n*n/k);
    return 0;
}
相关标签: BZOJ 点分治