codeforces-791D-Bear and Tree Jumps-树形dp

题目链接

好久没更新了……奇怪的py写完了，明天下午上台瞎说说晚上就能挂上来了（写的奇丑无比）……

题意：现在有一棵树，还有一只熊，这只熊每次可以从一个点跳到距离不超过k（k<=5）的点上。设f(x,y)表示从点x跳到y的最少次数，现让你求出所有点对(x,y),(其中x<y)的f值的和

思路：这题好难啊(其实是自己太菜了)……想得到是树形dp,但是想不出来怎么计数……日常看题解。
对于每一个点对，他们的贡献是[dis(x,y)/k],这个式子可以写成dis(x,y)/k+((k-dis(x,y)%k+k)%k)/k;后一项也就是把没达到k倍数的部分补全。
前一部分，我们先看dis(x,y)我们可以枚举每一条边，这条边指向的子树的个数乘上剩余点的个数，就是这条边的贡献。全部加起来最后再除以k就行了。
难的是第二部分，对于两个点x,y,我们当然不能爆搜。我们可以利用dfs后缀和的性质，将一棵子树中的所有点按%k的值保存。dp[i][j]表示以i为根节点的子树中与总根节点距离%k=j的节点的个数，那么对于一个点来说，他的所有子节点构成的子树只要以k^2复杂度相互计算就行了，以他本身为lca。这样既不会重复，也很好转移。这个不太好说，直接看代码比较容易。

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
44
45
46
47
48
49
#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
vector<int >g[200005];
long long dp[200005][10];
long long sum[200005];
long long n,m,k;
long long ans=0;
void dfs(int u,int fa,int deep)
{
	dp[u][deep%k]=1;
	sum[u]=1;
	int l=g[u].size();
	for(int i=0;i<l;i++)
	{
		int v=g[u][i];
		if(v==fa)continue;
		dfs(v,u,deep+1);
		for(int a=0;a<=k-1;a++)
		  for(int b=0;b<=k-1;b++)
		  {
		  	long long dis=((a+b)%k-(2*deep)%k+k)%k;
		  	long long gong=(k-dis+k)%k;
		  	ans=ans+gong*dp[u][a]*dp[v][b];
		  }
		ans+=sum[v]*(n-sum[v]);  
		sum[u]+=sum[v];
		for(int j=0;j<k;j++)dp[u][j]+=dp[v][j];
	}	
}
int main()
{
	scanf("%I64d%I64d",&n,&k);	
 	for(int i=1;i<=n-1;i++)
 	{
 		int u,v;
 		scanf("%d%d",&u,&v);
 		g[u].push_back(v);
 		g[v].push_back(u);
	 }
	dfs(1,-1,0);
	printf("%I64d\n",ans/k); 
	return 0;
 }