0 分点分治求条
查看原帖
0 分点分治求条
868864
zjinze楼主2024/3/16 07:18
#include <bits/stdc++.h>
using namespace std;
const int N=1e4+7;
int k,n,m,u,v,w,siz[N],cur,del[N],temp[N],tot=0,nn,lens[N],ans=0;
vector< pair<int,int> >ve[N];
void dfs1(int x,int fa){
	siz[x]=1;
	int ans=0; 
	for(int j=0;j<ve[x].size();j++){
		int to=ve[x][j].first;
		if(to==fa)continue;
		if(del[to])continue;
		dfs1(to,x);
		if(cur!=-1)return ;
		ans=max(ans,siz[to]);
		siz[x]+=siz[to];
	}
	ans=max(ans,n-siz[x]);
	if(ans<=n/2){
		cur=x;
		siz[fa]=n-siz[x];
	}
	return ;
}
void dfs2(int x,int fa,int len){
	temp[++tot]=len%3;
	lens[len%3]++;
	for(int j=0;j<ve[x].size();j++){
		int to=ve[x][j].first;
		int w=ve[x][j].second;
		if(del[to])continue;
		if(to==fa)continue;
		dfs2(to,x,len+w);
	}
}
void run(int x){
	for(int j=0;j<ve[x].size();j++){
		int to=ve[x][j].first;
		int w=ve[x][j].second;
		if(del[to])continue;
		int tmp=tot;
		dfs2(to,x,w);
		for(int i=1;i<=tmp;i++){
			for(int t=tmp+1;t<=tot;t++){
				lens[(temp[i]+temp[t])%3]++;
			}
		}
	}
	for(int i=1;i<=tot;i++)temp[i]=0;
	ans=ans+lens[0]*lens[0]+lens[1]*lens[2]*2;
	lens[0]=lens[1]=lens[2]=0;
	tot=0;
	del[x]=true;
	for(int j=0;j<ve[x].size();j++){
		int to=ve[x][j].first;
		int w=ve[x][j].second;
		if(del[to])continue;
		n=siz[to];
		cur=-1;
		dfs1(to,0);
		run(cur);
	}
	return ;
}
int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while (ch>='0' && ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
signed main(){
	n=read();
	nn=n*n;
	for(int i=1;i<n;i++){
		u=read();
		v=read();
		w=read();
		ve[u].push_back(make_pair(v,w));
		ve[v].push_back(make_pair(u,w));
	}
	cur=-1;
	dfs1(1,0);
	run(cur);
//	cout<<ans<<"\n";
	cout<<ans/__gcd(ans,nn)<<'/'<<nn/__gcd(ans,nn);
	return 0;
}
2024/3/16 07:18
加载中...