本文共 1463 字，大约阅读时间需要 4 分钟。

链接：https://ac.nowcoder.com/acm/problem/15748

来源：牛客网

题目描述

Cwbc和XHRlyb生活在s市，这天他们打算一起出去旅游。 旅行地图上有n个城市，它们之间通过n-1条道路联通。 Cwbc和XHRlyb第一天会在s市住宿，并游览与它距离不超过1的所有城市，之后的每天会选择一个城市住宿，然后游览与它距离不超过1的所有城市。 他们不想住在一个已经浏览过的城市，又想尽可能多的延长旅行时间。 XHRlyb想知道她与Cwbc最多能度过多少天的时光呢？ 聪明的你在仔细阅读题目后，一定可以顺利的解决这个问题！ 输入描述: 第一行，两个正整数n和s，表示城市个数和第一天住宿的城市s。 接下来n-1行，每行两个整数x和y，表示城市x与城市y之间有一条双向道路。 输出描述: 第一行，一个非负整数表示答案。 示例1 输入 复制 4 1 1 2 2 3 3 4 输出 复制 2 说明 第一天，在1号城市住宿，游览了1、2号城市。 第二天，在3号城市住宿，游览了4号城市，旅行结束。 备注: 1 ≤ n ≤ 500000, 1 ≤ s, x, y ≤ n。 算是树的最大独立集的一个模板题。 树的最大独立集，就是这样的一个集合，这些集合里面的点在树中互不相邻。 那么对于树中的每个节点就有两种状态，在最大独立集里面或者不在最大独立集里面。 状态转移方程: 如果这个点在独立集里面：dp[u][1]+=dp[to][0] (儿子节点一定不在最大独立集里面) 如果这个点不在独立集里面：dp[u][0]+=max(dp[to][1],dp[to][0])（儿子的两种状态取最优状态）。 这个题给定了一开始必须住的那一个城市，所以那一个城市一定在最大独立集里面。 代码如下：

#include
   
    #define ll long longusing namespace std;const int maxx=5e5+100;struct edge{
   	int to,next;}e[maxx<<1];int head[maxx<<1],tot;int dp[maxx][2];int n,s;/*------------事前准备-----------*/inline void init(){
   	memset(head,-1,sizeof(head));	tot=0;}inline void add(int u,int v){
   	e[tot].to=v,e[tot].next=head[u],head[u]=tot++;}/*------------树形dp求树的最大独立集-------------*/inline void dfs(int u,int f){
   	dp[u][0]=dp[u][1]=0;	for(int i=head[u];i!=-1;i=e[i].next)	{
   		int to=e[i].to;		if(to==f) continue;		dfs(to,u);		dp[u][1]+=dp[to][0];		dp[u][0]+=max(dp[to][1],dp[to][0]);	}	dp[u][1]++;//不要忘了把自己加进去}int main(){
   	int x,y;	while(~scanf("%d%d",&n,&s))	{
   		init();		for(int i=1;i
   

努力加油a啊，(^o)/~

转载地址：http://zutvi.baihongyu.com/