2152: 聪聪可可 点分治+特殊的技巧

2019-04-13 16:28发布

站内文章 / 模拟电子
14744 0 1369
裸的点分治
小技巧：判断边权之和为3的倍数时，我们可以对所有的边权取模，然后进行统计。答案为模3为1的个数*模3为2的个数*2+模3为0的个数的平方。 #include #include #include #include #define inf 1000000007 using namespace std; int n,cnt,ans,root,sum; int head[20005],size[20005],f[20005],d[20005],t[3]; bool vis[20005]; int list[40005],next[40005],key[40005]; inline int read() { int a=0,f=1; char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();} while (c>='0'&&c<='9') {a=a*10+c-'0'; c=getchar();} return a*f; } int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } inline void insert(int x,int y,int z) { next[++cnt]=head[x]; head[x]=cnt; list[cnt]=y; key[cnt]=z; } void getroot(int x,int fa) { size[x]=1; f[x]=0; for (int i=head[x];i;i=next[i]) if (list[i]!=fa&&!vis[list[i]]) { getroot(list[i],x); size[x]+=size[list[i]]; f[x]=max(f[x],size[list[i]]); } f[x]=max(f[x],sum-size[x]); if (f[x]void getdeep(int x,int fa) { t[d[x]]++; for (int i=head[x];i;i=next[i]) if (list[i]!=fa&&!vis[list[i]]) { d[list[i]]=(d[x]+key[i])%3; getdeep(list[i],x); } } inline int calc(int x,int now) { t[0]=t[1]=t[2]=0; d[x]=now; getdeep(x,0); return t[1]*t[2]*2+t[0]*t[0]; } void work(int x) { ans+=calc(x,0); vis[x]=1; for (int i=head[x];i;i=next[i]) if (!vis[list[i]]) { ans-=calc(list[i],key[i]); root=0; sum=size[list[i]]; getroot(list[i],0); work(root); } } int main() { n=read(); for (int i=1,u,v,w;i3,insert(u,v,w),insert(v,u,w); sum=n; f[0]=inf; getroot(1,0); work(root); int t=gcd(ans,n*n); printf("%d/%d",ans/t,n*n/t); return 0; }

热门文章