点分治求助,t了9,10,但重心没找错
查看原帖
点分治求助,t了9,10,但重心没找错
344847
Rubi_sama楼主2023/6/16 19:09
#include<bits/stdc++.h>
using namespace std;
#define re register
#define fo1(l,r) for(re int i=l;i<=r;++i)
#define fo2(l,r) for(re int j=l;j<=r;++j)
#define fo3(l,r) for(re int k=l;k<=r;++k)
#define fo4(l,r) for(re int tt=l;tt<=r;++tt)
#define fo(l) for(re int i=h[l],go;i;i=x[i].last)
#define inf 0x3f3f3f3f
#define INF 0x7fffffffffffffff
#define LL long long
#define itn int
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch))
	{
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
    while(isdigit(ch))
	{
		x=(x<<3)+(x<<1)+ch-48;
		ch=getchar();
	}
    return x*f;
}
const int N=2e4+10;
struct node
{
	int to,last,dis;
}x[N<<1];
int h[N],ss;
inline void Add(int xx,int yy,int zz)
{
	x[++ss].to=yy;
	x[ss].last=h[xx];
	x[ss].dis=zz;
	h[xx]=ss;
	return;
}
int f[N][3],s[3];
int siz[N];
int minn,bh;
bitset<N> pd;
int ANS1,ANS2;
inline int max2(int xx,itn yy)
{
	return xx>yy?xx:yy;
}
inline void zhongxin(itn now,itn fa)
{
	int maxn=-1;
	siz[now]=1;
	fo(now)
	{
		go=x[i].to;
		if(go!=fa && pd[go]==0)
		{
			zhongxin(go,now);
			siz[now]+=siz[go];
			maxn=max2(maxn,siz[go]);
		}
	}
	maxn=max2(maxn,siz[now]-maxn);
	if(maxn<minn)
	{
		minn=maxn;bh=now;
	}
	return;
}
inline void dfs(int now,int fa,int dep,int bb)
{
	fo(now)
	{
		go=x[i].to;
		if(go!=fa && pd[go]==0)
		{
			itn ty=(dep+x[i].dis)%3;
			++f[bb][ty];++s[ty];
			dfs(go,now,dep+x[i].dis,bb);
		}
	}
}
inline void dianfenzhi(int now,int sum)
{
	minn=inf;
	zhongxin(now,-1);
	int st=bh;
//	cout<<"当前节点是"<<st<<endl;
	int cnt=1;
	f[1][0]=1;f[1][1]=0;f[1][2]=0;s[0]=1;s[1]=0;s[2]=0;
	fo(st)
	{
		go=x[i].to;
		if(pd[go]==0)
		{
//			cout<<"扩展节点"<<go<<endl; 
			int ty=x[i].dis%3;
			f[++cnt][0]=0;f[cnt][1]=0;f[cnt][2]=0;
			++f[cnt][ty];
			++s[ty];
			dfs(go,st,x[i].dis,cnt);
		}
	}
//	cout<<"前"<<ANS1<<" "<<ANS2<<endl; 
	int ss0=0,ss1=0,ss2=0;
	fo1(1,cnt)
	{
		ss0+=f[i][0];
		ss1+=f[i][1];
		ss2+=f[i][2];
		ANS1+=(s[0]-ss0)*f[i][0]*2;
		ANS1+=(s[1]-ss1)*f[i][2]*2;
		ANS1+=(s[2]-ss2)*f[i][1]*2;
	}
//	cout<<"后"<<ANS1<<" "<<ANS2<<endl; 
	pd[st]=1;
	fo(st)
	{
		go=x[i].to;
		if(pd[go]==0)
		{
			dianfenzhi(go,siz[go]);
		}
	}
	return;
}
inline int ygcd(int xx,itn yy)
{
	return yy==0?xx:ygcd(yy,xx%yy);
}
int main()
{
	int n=read();
	fo1(1,n-1)
	{
		int ls1=read(),ls2=read(),ls3=read();
		Add(ls1,ls2,ls3);Add(ls2,ls1,ls3);
	}
	ANS1=n;
	ANS2=n*n;
	dianfenzhi(1,n);
	while(1)
	{
		int ls1=ygcd(ANS1,ANS2);
		if(ls1==1)
			break;
		ANS1/=ls1;
		ANS2/=ls1;
	}
	printf("%d/%d",ANS1,ANS2);
	return 0;
}
2023/6/16 19:09
加载中...