树【树形Dp】

题目描述

图论中的树为一个无环的无向图。给定一棵树,每个节点有一盏指示灯和一个按钮。如果节点的按扭被按了,那么该节点的灯会从熄灭变为点亮(当按之前是熄灭的),或者从点亮到熄灭(当按之前是点亮的)。并且该节点的直接邻居也发生同样的变化。

开始的时候,所有的指示灯都是熄灭的。请编程计算最少要按多少次按钮,才能让所有节点的指示灯变为点亮状态。

输入格式

输入文件有多组数据。

输入第一行包含一个整数n,表示树的节点数目。每个节点的编号从1到n。

输入接下来的n – 1行,每一行包含两个整数x,y,表示节点x和y之间有一条无向边。

当输入n为0时,表示输入结束。

输入样例

3 1 2 1 3 ## 输出样例: 1

输出格式

对于每组数据,输出最少要按多少次按钮,才能让所有节点的指示灯变为点亮状态。每一组数据独占一行。

表示以为根的子树都亮,并且
表示以为根的子辈都亮,没开,
表示以为根的子辈都亮,没开,不亮
初始t = 0
if()^
t = 0 代表着 i 不会亮,t = 1 就代表着 i 会亮



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
#include<bits/stdc++.h>
using namespace std;
#define add(x,y) edge[++tail]=(dd){head[x],y};head[x]=tail;
struct dd{
int ne,to;
}edge[500];
int head[111],tail,n;
long long f[111][3];
void dfs(int t,int fa){
f[t][0]=1;
int tt=0;
long long minn=1000000,s=0;
for(int i=head[t];i;i=edge[i].ne){
if(edge[i].to!=fa){
dfs(edge[i].to,t);
s+=min(f[edge[i].to][1],f[edge[i].to][0]);
if(f[edge[i].to][0]<f[edge[i].to][1])tt^=1;
minn=min(minn,abs(f[edge[i].to][1]-f[edge[i].to][0]));
f[t][0]+=f[edge[i].to][2];
}
}
f[t][1]=s+(tt?0:minn);
f[t][2]=s+(tt?minn:0);
}
int main(){
while(1){
scanf("%d",&n);
if(n==0)return 0;
memset(head,0,sizeof(head));
memset(f,0,sizeof(f));
tail=0;
for(int i=1,x,y;i<n;++i){
scanf("%d%d",&x,&y);
add(x,y);add(y,x);
}
dfs(1,1);
printf("%d\n",min(f[1][0],f[1][1]));
}
return 0;
}
发布于

2019-10-21

更新于

2021-09-26

许可协议

评论

:D 一言句子获取中...

加载中,最新评论有1分钟缓存...