題目鏈接

戳這

\(Solution\)

這道題看起來就像點分治對吧.沒錯就是點分治.
什么是點分治
如果你不會點分治,可以去看看這兒

現在看到這里,首先確保你已經會了點分治,如果不會你還往下看,聽不懂概不負責雖然會但沒看懂也不負責(逃)

點分治題目大部分都是模板對吧.只是calc(solve)的區(qū)別.首先看看暴力的calc.暴力枚舉所有邊,在判斷是否為3的倍數.

但是這顯然不行對吧,在仔細思考一下.發(fā)現%3的數的可能性只有三種情況

%3=0

%3=1

%3=2

所以想要為三的倍數的話有兩種可能性,0和0的組和,1和2的組合所以答案就是dis[1]*dis[2]*2+dis[0]*dis[0]最后的答案就是這個出以總方案數.記得約分.

\(Code\)

// luogu-judger-enable-o2 #include<bits/stdc++.h> using namespace std; const int N=40001; int read() {int x=0,f=1;char c=getchar();while(c<'0'||c>'9')c=='-'?f=-1,c=getchar():c=getchar();while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();return x*f; } int n,k; int dep[N]; int f[N]; int vis[N]; int siz[N]; int root; struct node {int next,to,v; } a[N<<1]; int head[N],cnt,sum; void add(int x,int y,int c) {a[++cnt].to=y;a[cnt].next=head[x];a[cnt].v=c;head[x]=cnt; } void findroot(int k,int fa) {f[k]=0,siz[k]=1;for(int i=head[k]; i; i=a[i].next) {int v=a[i].to;if(vis[v]||v==fa)continue;findroot(v,k);siz[k]+=siz[v];f[k]=max(f[k],siz[v]);}f[k]=max(f[k],sum-siz[k]);if(f[k]<f[root])root=k; } int tot; void finddep(int k,int fa,int l) {dep[l]++;for(int i=head[k]; i; i=a[i].next) {int v=a[i].to;if(v==fa||vis[v])continue;finddep(v,k,(l+a[i].v)%3);} } int calc(int k,int L) {tot=0;dep[0]=dep[1]=dep[2]=0;finddep(k,0,L%3);return dep[0]*dep[0]+2*dep[1]*dep[2]; } int js; void devide(int k) {vis[k]=1;js+=calc(k,0);for(int i=head[k]; i; i=a[i].next) {int v=a[i].to;if(vis[v])continue;js-=calc(v,a[i].v);root=0,sum=siz[v];findroot(v,0);devide(root);} } int main() {int n=read(),x,y,z;for (int i=1; i<n; i++)x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z);sum=f[0]=n;findroot(1,0);devide(root);int l=__gcd(js,n*n);printf("%d/%d\n",js/l,n*n/l);return 0; }

轉載于:https://www.cnblogs.com/hbxblog/p/9840188.html

總結

以上是生活随笔為你收集整理的「BZOJ 2152」聪聪可可的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。