静态点分治
一开始还以为要把分治树建出来……
• 树的结构不发生改变,点权边权都不变,那么我们利用刚刚的思路,有两种具体的分治方法。
• A:朴素做法,直接找重心,处理过重心的所有路径。然而,路径端点在同一子树(即路径实际上并不过重心)的情况会发生重复计数,需要使用类似容斥的方法,不断删去重复计数的部分。
• B:采用类似树形背包的思路,遍历子树时,只考虑当前子树和先前处理完的多颗子树之间的路径,以保证路径端点在不同的子树中,防止重复计数,不需要麻烦的容斥。在一些更为复杂的情况下,方法A不能解决问题,可以在方法B的基础上结合数据结构来解决。因此,方法B适用范围更广,细节更少不易错(个人观点),推荐大家使用。
感觉桶比较难以理解……容斥就是先更新整颗树的答案，然后处理lca是子树的答案。
#include<iostream>
#include<cstring>
#include<cstdio>
#define MAXN 20010
#define LL long long
#define INF 1000000000
using namespace std;
struct edge
{
int u,v,w,nxt;
#define u(x) ed[x].u
#define v(x) ed[x].v
#define w(x) ed[x].w
#define n(x) ed[x].nxt
}ed[MAXN*2];
int first[MAXN],num_e;
#define f(x) first[x]
int n;
int sum,mn,root;
int size[MAXN],mxsize[MAXN];
bool v[MAXN];
LL ans,cnt[3];
void getroot(int x,int fa)//找根节点
{
size[x]=1,mxsize[x]=0;
for(int i=f(x);i;i=n(i))
if(v(i)!=fa&&!v[v(i)])
{
getroot(v(i),x);
size[x]+=size[v(i)];
mxsize[x]=max(mxsize[x],size[v(i)]);
}
mxsize[x]=max(mxsize[x],sum-size[x]);
if(mxsize[x]<mn)mn=mxsize[x],root=x;
}
void ask(int x,int fa,int l)
{
cnt[l%3]++;
for(int i=f(x);i;i=n(i))
if(v(i)!=fa&&!v[v(i)])
ask(v(i),x,(l+w(i))%3);
}
int solve(int x,int add)
{
cnt[0]=cnt[1]=cnt[2]=0;
ask(x,0,add);
return 2ll*cnt[1]*cnt[2]+cnt[0]*cnt[0];
}
void divide(int x)
{
ans+=solve(x,0),v[x]=1;//更新答案
for(int i=f(x);i;i=n(i))
if(!v[v(i)])
{
ans-=solve(v(i),w(i));//容斥去重
sum=size[v(i)],mn=INF;
getroot(v(i),0);
divide(root);
}
}
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
inline void add(int u,int v,int w);
inline int read()
{
int s=0;char a=getchar();
while(a<'0'||a>'9')a=getchar();
while(a>='0'&&a<='9'){s=s*10+a-'0',a=getchar();}
return s;
}
signed main()
{
cin>>n;
int u,v,w;
for(int i=1;i<n;i++)
{
u=read(),v=read(),w=read();
add(u,v,w%3);add(v,u,w%3);
}
sum=n;mn=INF;
getroot(1,0);
divide(root);
LL fm=n*n;
int GCD=gcd(ans,fm);
printf("%lld/%lld\n",ans/GCD,fm/GCD);
}
inline void add(int u,int v,int w)
{
++num_e;
u(num_e)=u;
v(num_e)=v;
w(num_e)=w;
n(num_e)=f(u);
f(u)=num_e;
}