hdu 4714 Tree2cycle

本文从WordPress迁移而来, 查看全部WordPress迁移文章

树dp

题意:给一个无根树,每次可以删除一条边,或者两点间添加一条边(不是重边自环),使得最后整个树变为一个环,删除和加边花费都是1,问成环要付出的最小花费

有一个性质想明白了,就简单了

最后要成环,说明整个树就是一个直链,然后在链的两端加一条边就成环了,所以我们只需要知道整个树变为一条链的最小代价,然后+1就是答案。而一个子树是一条链,有两种可能,一种是这种形状”|”,一种是”^”,它们其实都是链,只是看起来形状不同,并且,和父亲连接的点不同,”|”是端点和父亲连接,”^”是中间的某个点和父亲连

设置dp[u][0]表示将u为根的子树变为”|”的最小花费,dp[u][1]表示将u为根的子树变为”^”的最小花费

最后的总花费就是 min(dp[1][0] , dp[1][1]) + 1;

现在来考虑转移

“|”形状表示,根u的下面还是一条链,”^”表示根u下面有2条链连在u上

对于u而言,如果它下面有多个分支,那么3步

  1. 将某个分支变为”|”或”^”
  2. 将这个分支和u断开
  3. 将这个分支和别的分支连起来

所以看起来转移就是

dp[u][0] = dp[u][1] = sigma (min(ddp[v][0] , dp[v][1]) + 2);

但要注意一个问题

如果u为根的子树最后就是变为”|”,那么可能有个分支,并不需要一开始的时候断开与根连接

也就是说,对于某个分支v

可能cost[v][0] > cost[v][1],那么就应该选”^”吗?不是的,因为选了”^”,最后还必须加上2花费(1断开1连接),但是选了cost[v][0],则可以省掉2个花费,所以判断的标准应该是

cost[v][0] 与 cost[v][1] + 2

这里不再详细说了,反而可能更乱,直接看代码吧

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
#pragma comment(linker,"/STACK:102400000,102400000")
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 1000010
#define INF 10000000
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int n,tot,head[N];
struct edge{
int u,v,next;
}e[2*N];

int son[N];
int cost[N][2];

inline void add(int u,int v){
e[tot].u = u; e[tot].v = v;
e[tot].next = head[u]; head[u] = tot++;
}

void dfs(int u,int fa){
cost[u][0] = cost[u][1] = 0;
son[u] = 0;
int delta1 = -INF , delta2 = -INF;
for(int k = head[u]; k != -1; k = e[k].next){
int v = e[k].v;
if(v == fa) continue;
son[u]++;
dfs(v,u);
cost[u][0] += (min(cost[v][0],cost[v][1])+2);
cost[u][1] += (min(cost[v][0],cost[v][1])+2);
if(cost[v][0] <= cost[v][1]+2){
int tmp = cost[v][1]+2 - cost[v][0];
if(tmp > delta1){ delta2 = delta1; delta1 = tmp;}
else if(tmp > delta2) { delta2 = tmp; }
}
}
if(delta1 != -INF){
delta1 = (delta1 > 2) ? 2 : delta1;
cost[u][0] -= delta1;
cost[u][1] -= delta1;
if(delta2 != - INF){
delta2 = (delta2 > 2) ? 2 : delta2;
cost[u][1] -= delta2;
}
}
}

int main(){
int T;
scanf("%d",&T);
while(T--){
tot = 0; cl(head,-1);
scanf("%d",&n);
for(int i = 1; i < n; i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v); add(v,u);
}
dfs(1,-1);
printf("%d\n",min(cost[1][0],cost[1][1])+1);
}
return 0;
}