思路：点分治
提交：1次
题解：
不需要什么容斥。。。接着板子题说：
还是基本思路：对于一颗子树，与之前的子树做贡献。
我们把路径的权值在(\%3)意义下分类，即开三个桶(c[0],c[1],c[2]),分别记录每一类的路径条数。合并的时候显然有:
[c[0]cdot mem[0]cdot 2+c[1]cdot mem[2]cdot 2+c[2]cdot mem[1]cdot 2
]
其中(mem[0],mem[1],mem[2])代表已经遍历的子树中每一类的路径条数。
代码：
#include<bits/stdc++.h>
#define R register int
using namespace std;
namespace Luitaryi {
template<class I> inline I g(I& x) { x=0; register I f=1;
register char ch; while(!isdigit(ch=getchar())) f=ch=='-'?-1:f;
do x=x*10+(ch^48); while(isdigit(ch=getchar())); return x*=f;
} const int N=20010,Inf=1e+9;
int n,m,cnt,rt,sum,ans; bool vis[N];
int vr[N<<1],nxt[N<<1],w[N<<1],fir[N],d[N],sz[N],c[3],mem[3],mx[N];
inline void add(int u,int v,int ww) {
vr[++cnt]=v,nxt[cnt]=fir[u],w[cnt]=ww,fir[u]=cnt;
vr[++cnt]=u,nxt[cnt]=fir[v],w[cnt]=ww,fir[v]=cnt;
}
inline void getsz(int u,int fa) {
sz[u]=1,mx[u]=0;
for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];
if(v==fa||vis[v]) continue;
getsz(v,u); sz[u]+=sz[v];
mx[u]=max(mx[u],sz[v]);
} mx[u]=max(mx[u],sum-sz[u]);
if(mx[u]<mx[rt]) rt=u;
}
inline void getdis(int u,int fa) {
++c[d[u]]; for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];
if(v==fa||vis[v]) continue;
d[v]=(d[u]+w[i])%3; getdis(v,u);
}
}
inline int calc() {
return c[0]*mem[0]*2+c[1]*mem[2]*2+c[2]*mem[1]*2;
}
inline void solve(int u,int fa) { vis[u]=true; mem[0]=1;
for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];
if(v==fa||vis[v]) continue;
d[v]=w[i]%3; getdis(v,u);
ans+=calc(),mem[0]+=c[0],mem[1]+=c[1],mem[2]+=c[2];
memset(c,0,sizeof(c));
} memset(mem,0,sizeof(mem));
for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];
if(v==fa||vis[v]) continue;
sum=sz[v],rt=0,mx[rt]=Inf;
getsz(v,u),getsz(rt,-1),solve(rt,u);
}
}
inline void main() {
g(n); for(R i=1,u,v,w;i<n;++i) g(u),g(v),g(w),add(u,v,w);
sum=n,mx[rt]=Inf; getsz(1,-1),getsz(rt,-1),solve(rt,-1); ans+=n;
R tmp=__gcd(ans,n*n); printf("%d/%d
",ans/tmp,n*n/tmp);
}
} signed main() {Luitaryi::main(); return 0;}
2019.08.31
69