- 题目链接：旅游
- 如果没有权限查看题目，请看下图
- 题目思路：根据题意，我们可以知道城市布局为一棵树，因为住宿在一个城市中可以游览与它距离为1的所有城市，那么相当于求一颗树的最大独立集。
- 关于如何求树的最大独立集：树形dp，用一个数组f[i][0或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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
using namespace std;
int sc() {
int xx=0,ff=1; char cch=gc;
while(cch<'0'|| cch>'9') {
if(cch=='-') ff=-1; cch=gc;
}
while(cch>='0'&& cch<='9') {
xx=(xx<<1)+(xx<<3)+(cch^'0'); cch=gc;
}
return xx*ff;
}
struct TREE {
int next,to;
}tree[Maxn<<1];
int n,s,cnt;
int head[Maxn<<1];
int f[Maxn][2];
void ADD(int from,int to) {
tree[++cnt].next=head[from];
tree[cnt].to=to;
head[from]=cnt;
}
void dfs(int son,int fa) {
f[son][0]=0;
f[son][1]=1;
for(int i=head[son]; i; i=tree[i].next) {
int to=tree[i].to;
if(to!=fa) {
dfs(to,son);
f[son][0]+=max(f[to][0],f[to][1]);
f[son][1]=max(f[son][1],f[son][1]+f[to][0]);
}
}
}
int main() {
int size = 64 << 20;
char *p = (char*)malloc(size) + size;
__asm__("movq %0, %%rsp\n" :: "r"(p));
n=sc(); s=sc();
for(int i=1; i<=n-1; i++) {
int x=sc(),y=sc();
ADD(x,y); ADD(y,x);
}
dfs(s,-1);
printf("%d\n",f[s][1]);
exit(0);
}