Description

Input

Output

Sample Input

Sample Output

HINT

不知道是不是因为我太弱了，感觉这道题真是一道好题。

首先如果是一棵树，那就是 没上司的晚会（著名树形DP）

但现在变成了环，不过并不重要！

我们可以在环上任取一条边，然后剪断他，记两端点为S,T

所以有以下两种情况：

S不选，T随意。

T不选，S随意。

就变成了 没上司的晚会！

#include <cstdio>
#include <algorithm>
#define maxn 1000010
#define ll long long
using namespace std;
ll v[maxn],g[maxn],f[maxn],ans;
int h[maxn<<1],last[maxn<<1],head[maxn],vis[maxn],S,T,E,l;
void add(int x,int y)
{
	h[++l] = y;
	last[l] = head[x];
	head[x] = l;
}

void dfs(int x,int fa)
{
	vis[x] = 1;
	for (int i = head[x];i;i = last[i])
		if (h[i] != fa)
		{
			if (vis[h[i]])
			{
				S = x;
				T = h[i];
				E = i;
			}
			else dfs(h[i],x);
		}
}
int inver(int x)
{
	return ((x-1)^1)+1;
}

void Tree_DP(int x,int fa,int ban)
{
	f[x]=v[x],g[x]=0;
	for(int i = head[x];i;i = last[i])
	{
		if( i==ban || inver(i)==ban )continue;
		if(h[i] == fa)continue;
		Tree_DP(h[i],x,ban);
		f[x]+=g[h[i]];
		g[x]+=max(f[h[i]],g[h[i]]);
	}
}
int main()
{
	int n;
	scanf("%d",&n);
	for (int i = 1;i <= n;i++)
	{
		int y;
		scanf("%lld%d",&v[i],&y);
		add(i,y);
		add(y,i);
	}
	for (int i = 1;i <= n;i++)
		if (!vis[i])
		{
			dfs(i,0);
			Tree_DP(S,0,E);
			ll temp=g[S];
			Tree_DP(T,0,E);
			temp=max(temp,g[T]);
			ans+=temp;
		}
	printf("%lld",ans);
	return 0;
}

我的DP能力还是有待提高，看来还是得多膜蛤。

另外bzoj2152 也是一道树形DP的基础题（TM还是要看题解）

附上代码

#include <cstdio>
#define maxn 20010
int dp[maxn][3],h[maxn*2],v[maxn*2],last[maxn*2],head[maxn],l,vis[maxn],ans;
void add(int x,int y,int z)
{
	h[++l] = y;
	v[l] = z % 3;
	last[l] = head[x];
	head[x] = l;
}

void dfs(int x)
{
	vis[x] = 1;
	dp[x][0]++;
	for (int i = head[x];i;i = last[i])
		if (!vis[h[i]])
		{
			dfs(h[i]);
			for (int j = 0;j <= 2;j++)
				ans += dp[x][j]*dp[h[i]][(6-v[i]-j)%3],dp[x][j] += dp[h[i]][(6-v[i]+j)%3]; 
		}
}
int gcd(int x,int y)
{
	if (x % y==0) return y;
	return gcd(y,x%y);
}
int main()
{
	int n;
	scanf("%d",&n);
	for (int i = 1;i < n;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
	}
	dfs(1);
	ans = ans*2+n;
	int l = gcd(ans,n*n);
	printf("%d/%d",ans/l,n*n/l);
	return 0;
}