1021 -点分治 - 聪聪可可（BZOJ 2152）

传送门

题意

给定一棵边带权树，问有多少个点对，其简单路径上的权值和为3的倍数

分析

这和之前做过的Tree POJ 1741有异曲同工之妙，解决树上的点对（路径）关系，我们自然想到了分治算法
问题就变得简单起来，我们只需要思考如何统计路径和为3的倍数的点对，其他的就按照点分治的一般套路走
上一道例题，我们是记录的dis[i]，表示 i 这个点到重心的距离，然后按距离排序，二分，求得方案数
搬到这道题上，显然行不通了，如果还是按同样的定义，我们就只能n²统计（n ☞ 点的个数）
怎么办呢？我也不知道啊
但题解知道：统计一下每个点到重心的距离模 3 后的值出现的次数，即 sum[i] 就表示到重心路径模 3 为 i 的点的总数（当然 i 只可能为 0，1 或者 2 ）
那么总共的 ans=sum0∗sum0+2∗sum1∗sum2
​还要乘 2 的原因是顺序不同的点对是不同的（比如 (2,3),(3,2) 是不同的）
当然由于重复计算，在递归到子树时，还要将部分答案减掉
而总情况显然是 n²

代码

#include<bits/stdc++.h>
#define in  read()
#define N 20009
using namespace std;
inline int read(){
	char ch;int f=1,res=0;
	while((ch=getchar())<'0'||ch>'9') if(ch=='-') f=-1;
	while(ch>='0'&&ch<='9'){
		res=(res<<3)+(res<<1)+ch-'0';
		ch=getchar();
	}
	return f==1?res:-res;
}
int n,maxn,ans=0,sum[5],G; 
int nxt[N<<1],to[N<<1],head[N],w[N<<1],cnt=0;
int sze[N],son[N];
bool vis[N];
void add(int x,int y,int z){
	nxt[++cnt]=head[x];head[x]=cnt;to[cnt]=y;w[cnt]=z;
	nxt[++cnt]=head[y];head[y]=cnt;to[cnt]=x;w[cnt]=z;
}
int gcd(int x,int y){
	int z=x%y;
	while(z){x=y;y=z;z=x%y;}
	return y;
}
void getsize(int u,int fu){
	sze[u]=1;son[u]=0;
	for(int e=head[u];e;e=nxt[e]){
		int v=to[e];
		if(!vis[v]&&v!=fu){
			getsize(v,u);
			sze[u]+=sze[v];
			if(sze[v]>son[u]) son[u]=sze[v];
		}
	}
}
void getG(int rt,int u,int fu){//based on now
	son[u]=max(son[u],sze[rt]-sze[u]);
	if(son[u]<maxn){
		maxn=son[u];
		G=u;
	}
	for(int e=head[u];e;e=nxt[e]){
		int v=to[e];
		if(!vis[v]&&v!=fu)	getG(rt,v,u);
	}
}
void getdis(int u,int fu,int d){
	sum[d%3]++;
	for(int e=head[u];e;e=nxt[e]){
		int v=to[e];
		if(!vis[v]&&v!=fu){
			getdis(v,u,d+w[e]);
		}
	}
}
int calc(int u,int L){
	memset(sum,0,sizeof(sum));
	getdis(u,0,L);
	return sum[0]*sum[0]+sum[1]*sum[2]*2;
}
void solve(int u){
	maxn=n;
	getsize(u,0);
	getG(u,u,0);
	vis[G]=1;
	ans+=calc(G,0);
	for(int e=head[G];e;e=nxt[e]){
		int v=to[e];
		if(!vis[v]){
			ans-=calc(v,w[e]);
			solve(v);
		}
	}
}
int main(){
	n=in;
	int i,j,k;
	for(i=1;i<n;++i){
		int x=in,y=in,w=in;
		add(x,y,w);
	}
	solve(1);
	n*=n;
	int gd=gcd(ans,n);
	ans/=gd;n/=gd;
	printf("%d/%d",ans,n);
	return 0;
}