0 分淀粉质求调
查看原帖
0 分淀粉质求调
868864
zjinze楼主2024/3/15 22:15
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e4+5;
int nn,w,tot=0,n,k,siz[N],x,y,temp[N],cur,m,ans;
bool del[N];
map<int,int>lens;
vector< pair<int,int> >ve[N];
void dfs1(int x,int fa){
	siz[x]=1;
	int maxs=0;
	for(int j=0;j<ve[x].size();j++){
		int to=ve[x][j].first;
		int w=ve[x][j].second;
		if(to==fa)continue;
		if(del[to])continue;
		dfs1(to,x);
		if(cur!=-1)return ;
		maxs=max(maxs,siz[to]);
		siz[x]+=siz[to];		
	}
	maxs=max(maxs,n-siz[x]);
	if(maxs<=n/2){
		cur=x;
		siz[fa]=n-siz[x];
	}
	return ;
}
void dfs2(int x,int fa,int len){
	temp[++tot]=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);
	}
	return ;
}
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);
		ans=ans+lens[0]*lens[0]+lens[1]*lens[2]*2;
		for(int i=tmp+1;i<=tot;i++){
			lens[temp[i]]++;
		}
		tot=0;
	}
//	cout<<x<<" "<<ans<<"\n"; 
	lens.clear();
	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;
		cur=-1;
		n=siz[to];
		dfs1(to,x);
		run(cur);
	}
	return ;
}
signed main(){
	cin>>n;
	nn=n*n;
	for(int i=1;i<n;i++){
		cin>>x>>y>>w;
		ve[x].push_back(make_pair(y,w));
		ve[y].push_back(make_pair(x,w));
	}
	cur=-1;
	dfs1(1,1); 
	run(cur);
//	cout<<ans<<"\n";
	cout<<ans/__gcd(ans,nn)<<"/"<<nn/__gcd(ans,nn);
	return 0;
}
2024/3/15 22:15
加载中...