点分治,觉得思路没有问题,但是样例过不去
查看原帖
点分治,觉得思路没有问题,但是样例过不去
360511
UperFicial楼主2022/5/12 14:29
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<cctype>
#include<stack>
#include<map>
#include<climits>
#include<set>
#include<iostream>
#define rint() read<int>()
#define rll() read<ll>()
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define rev(i,a,b) for(register int i=a;i>=b;--i)
#define gra(i,u) for(register int i=head[u];i;i=edge[i].nxt)
#define Clear(a) memset(a,0,sizeof(a))
using namespace std;
typedef long long ll;
inline int read()
{
	register int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')s=s*10+(ch-'0'),ch=getchar();
	return s*w;
}
const int INF=1e9;
const ll LLINF=1e18;
template<typename T>
inline T Min(T x,T y){return x<y?x:y;}
template<typename T>
inline T Max(T x,T y){return x>y?x:y;}
template<typename T>
inline void Swap(T&x,T&y){int t=x;x=y;y=t;return;}
const int MAXN(2e4+10);
int n;
struct E{int to,nxt,cost;};
E edge[MAXN<<1];
int head[MAXN],tot;
inline void add_edge(int u,int v,int w)
{
	edge[++tot].nxt=head[u];
	head[u]=tot;
	edge[tot].to=v;
	edge[tot].cost=w;
	return;
} 
int dp[MAXN],S,siz[MAXN],root;
bool vis[MAXN];
int res[MAXN],num,d[MAXN];
int mp[4];
inline void get_root(int u,int fa)
{
	siz[u]=1,dp[u]=0;
	gra(i,u)
	{
		E e=edge[i];
		if(e.to==fa||vis[e.to]) continue;
		get_root(e.to,u);
		siz[u]+=siz[e.to];
		dp[u]=Max(dp[u],siz[e.to]);
	}
	dp[u]=Max(dp[u],S-siz[u]);
	if(dp[u]<dp[root]) root=u;
	return;
}
inline void get_dis(int u,int fa)
{
	res[++num]=d[u];
	gra(i,u)
	{
		E e=edge[i];
		if(e.to==fa||vis[e.to]) continue;
		d[e.to]=(d[u]+e.cost)%3;
		get_dis(e.to,u);
	}
	return;
}
int ans;
inline void solve(int u)
{
	++mp[0];
	gra(i,u)
	{
		E e=edge[i];
		if(vis[e.to]) continue;
		d[e.to]=e.cost%3,num=0;
		get_dis(e.to,u);
		rep(j,1,num)
		{
			if(res[j]==0) ans=ans+1+mp[0]*2;
			else if(res[j]==1) ans=ans+mp[2]*2;
			else if(res[j]==2) ans=ans+mp[1]*2; 
		}
		rep(j,1,num) mp[res[j]]++;
	}
	mp[0]=0,mp[1]=0,mp[2]=0;
	return; 
}
inline void dfs(int u)
{
	vis[u]=true,solve(u);
	gra(i,u)
	{
		E e=edge[i];
		if(vis[e.to]) continue;
		root=0,dp[0]=n,S=siz[e.to];
		get_root(e.to,u);
		dfs(root);
	}
	return;
}
inline int gcd(int x,int y){return y==0?x:gcd(y,x%y);}
int main()
{
	n=read();
	rep(i,1,n-1)
	{
		int u=read(),v=read(),w=read();
		add_edge(u,v,w);
		add_edge(v,u,w);
	}
	root=0,dp[0]=n,S=n;
	get_root(1,0);
	dfs(root);
	int a=ans-1,b=n*n;
	int g=gcd(a,b);
	a/=g,b/=g;
	printf("%d/%d\n",a,b);
	return 0;
}
2022/5/12 14:29
加载中...