JZOJ 5496 Tree（点分治+树形dp）

发表于 |
字数统计: 1,241字 | 阅读时长 ≈ 7min

Tree

Description

从前有棵树。
找出 k 个点 A 1 , A 2 , · · · , A k 。
∑ k−1
使得 i=1 dis(A i A i+1 ) 最小。

Input

第一行两个正整数 n, k, 表示数的顶点数和需要选出的点个数。
接下来 n − 1 行每行 3 个非负整数 x, y, z, 表示从存在一条从 x 到 y 权值为 z 的边。
1 ≤ k ≤ n。
1 ≤ x, y ≤ n。
1 ≤ z ≤ 10 5 。

Output

一行一个整数, 表示最小的距离和。

Scoring

对于 10% 的数据, n ≤ 10。
对于另外 10% 的数据, k = n。
对于另外 20% 的数据, n ≤ 50。
对于另外 20% 的数据, n ≤ 200。
对于 100% 的数据, n ≤ 3000。

标解是直接dp，但也可以点分治。
首先注意到答案一定是一个树上联通块，那么点分治后只需要考虑包含根的联通块，那么转化成一个树形依赖dp。
另外需要注意到最终的答案在点分治下，可以存在两条从根出发的链只走一次，其他的需要走两次。
令$F[x][y][0/1]$表示以x为根，选y个点，是否存在从根出发只走一次的链，
那么对于每个点$F[x][1][0]=2*d,F[x][1][1]=d$，d表示从他父亲到他的边长。
有转移
$$
F[x][y+k][0]=min(F[son][k][0]+F[x][y][0])
$$

$$
F[x][y+k][1]=min(F[son][k][0]+F[x][y][1],F[son][k][1]+F[x][y][0]-d)
$$

最后在根节点做一次背包，$G[x][k]$表示选了$x$个点，其中有$k$条只走一次的链$k=0,1,2$，这个直接背包就行。
最后答案取$min(G[m][0],G[m][1],G[m][2])$

复杂度很玄学，不知道。但跑得飞快。

这道题最关键的地方是，dp跑for循环的时候,一定只枚举子树size的前缀和，并且不要写$F[x][y-k]$，$F[x][y+k]$要快的多。具体可以看代码的注释

代码：

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 3005
using namespace std;
int n,m,Min,rt,Ans,si[N],F[N][2][N],G[3][N];
bool mark[N];
int TOT,LA[N],NE[N<<1],EN[N<<1],LE[N<<1];
void ADD(int x,int y,int z)
{
	TOT++;
	EN[TOT]=y;
	LE[TOT]=z;
	NE[TOT]=LA[x];
	LA[x]=TOT;
}
void Gsi(int x,int f)
{
	int i,y;si[x]=1;
	for(i=LA[x];i;i=NE[i])
	{
		y=EN[i];
		if(y==f||mark[y])continue;
		Gsi(y,x);si[x]+=si[y];
	}
}
void Grt(int x,int s,int f)
{
	int i,y,Max=s-si[x];
	for(i=LA[x];i;i=NE[i])
	{
		y=EN[i];
		if(y==f||mark[y])continue;
		Grt(y,s,x);Max=max(Max,si[y]);
	}
	if(Max<Min)Min=Max,rt=x;
}
void DP(int x,int d,int f)
{
	int i,j,k,y,sum=1;
	fill(F[x][0],F[x][0]+si[x]+1,1e9);
	fill(F[x][1],F[x][1]+si[x]+1,1e9);
	F[x][0][1]=2*d;F[x][1][1]=d;
	for(i=LA[x];i;i=NE[i])
	{
		y=EN[i];if(mark[y]||y==f)continue;
		DP(y,LE[i],x);
		if(sum>m)sum=m;
		for(j=sum;j>=1;j--)//跑得慢的写法是for(j=sum+si[y];j>=2;j--)F[x][1][j-k]=min()
		for(k=1;k<=si[y];k++)
		{
			F[x][1][j+k]=min(F[x][1][j+k],F[x][0][j]+F[y][1][k]-d);
			F[x][1][j+k]=min(F[x][1][j+k],F[x][1][j]+F[y][0][k]);
		}
		for(j=sum;j>=1;j--)//同理
		for(k=1;k<=si[y];k++)F[x][0][j+k]=min(F[x][0][j+k],F[x][0][j]+F[y][0][k]);
		sum+=si[y];
	}
}
void Gans(int x)
{
	int i,j,k,p,y,sum=1;
	memset(G,60,sizeof(G));
	G[0][1]=G[1][1]=G[2][1]=0;Gsi(x,0);
	for(i=LA[x];i;i=NE[i])
	{
		y=EN[i];if(mark[y])continue;
		DP(y,LE[i],x);
		if(sum>m)sum=m;
		for(k=sum;k>=1;k--)//同理
		for(p=1;p<=si[y];p++)
		{
			G[2][k+p]=min(G[2][k+p],G[1][k]+F[y][1][p]);
			G[2][k+p]=min(G[2][k+p],G[2][k]+F[y][0][p]);
		}
		for(k=sum;k>=1;k--)//同理
		for(p=1;p<=si[y];p++)
		{
			G[1][k+p]=min(G[1][k+p],G[0][k]+F[y][1][p]);
			G[1][k+p]=min(G[1][k+p],G[1][k]+F[y][0][p]);
		}
		for(k=sum;k>=1;k--)//同理
		for(p=1;p<=si[y];p++)G[0][k+p]=min(G[0][k+p],G[0][k]+F[y][0][p]);
		sum+=si[y];
	}
	Ans=min(Ans,G[0][m]);
	Ans=min(Ans,G[1][m]);
	Ans=min(Ans,G[2][m]);
}
void DC(int x)
{
	int i,y;mark[x]=1;
	Gans(x);
	for(i=LA[x];i;i=NE[i])
	{
		y=EN[i];
		if(mark[y])continue;
		Min=1e9;Gsi(y,x);
		Grt(y,si[y],x);DC(rt);
	}
}
int main()
{
	int i,j,k,x,y,z;
	scanf("%d%d",&n,&m);
	for(i=1;i<n;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		ADD(x,y,z);ADD(y,x,z);
	}
	Ans=1e9;
	Min=1e9;Gsi(1,0);Grt(1,n,0);DC(rt);
	printf("%d",Ans);
}