「国家集训队」聪聪可可

发表于 | 分类于 | | 浏览量： 次

我数数最差了QwQ…

传送门

洛谷P2634

BZOJ2152

题解

很显然这是一道假的概率题。而是一道数数题，只要数出路径长度为3的倍数的点对的数量就行了呢poi。

隔壁dalao说这是一道点分治裸题，但是我还是觉得树形DP更好写一些QwQ。

定义$F_{ij}(j \in \lbrace 0,1,2 \rbrace)$表示节点$i$的子树中，到i的距离$\mod 3=j$的节点个数。如果当前遍历到的节点为i，我们需要计算出$i$及其子树中满足最短路径经过节点$i$且满足路径长是3的倍数的节点个数，累计到答案里最后除以$n^2$并约分就好了呢poi。

注意起点和终点可以相同，计算时小心点，不要算重复也不要漏算了哟poi。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<cstdio>
using namespace std;
const int maxn=20005;
int n,tot,lnk[maxn],son[maxn*2],w[maxn*2],nxt[maxn*2],F[maxn][3],ans1,ans2;
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
inline void add_e(int x,int y,int z){tot++;son[tot]=y;w[tot]=z;nxt[tot]=lnk[x];lnk[x]=tot;}
int gcd(int x,int y){return !y?x:gcd(y,x%y);}
void DFS(int now,int fa)
{
	F[now][0]=1;
	for(int i=lnk[now];i;i=nxt[i])
	{
		if(son[i]!=fa)
		{
			DFS(son[i],now);
			for(int j=0;j<3;j++)
				ans1+=F[son[i]][j]*F[now][((3-j-w[i])%3+3)%3]*2;
			for(int j=0;j<3;j++)
				F[now][(j+w[i])%3]+=F[son[i]][j];
		}
	}
}
int main()
{
	n=read();
	for(int i=1;i<n;i++)
	{
		int a=read(),b=read(),c=read();
		add_e(a,b,c);add_e(b,a,c);
	}
	DFS(1,0);
	ans1+=n;ans2=n*n;
	int gys=gcd(ans1,ans2);
	ans1/=gys;ans2/=gys;
	printf("%d/%d\n",ans1,ans2);
	return 0;
}