链接：https://ac.nowcoder.com/acm/problem/13249
来源：牛客网
题目描述
一棵n个点的有根树，1号点为根，相邻的两个节点之间的距离为1。树上每个节点i对应一个值k[i]。每个点都有一个颜色，初始的时候所有点都是白色的。
你需要通过一系列操作使得最终每个点变成黑色。每次操作需要选择一个节点i，i必须是白色的，然后i到根的链上（包括节点i与根）所有与节点i距离小于k[i]的点都会变黑，已经是黑的点保持为黑。问最少使用几次操作能把整棵树变黑。
你需要通过一系列操作使得最终每个点变成黑色。每次操作需要选择一个节点i，i必须是白色的，然后i到根的链上（包括节点i与根）所有与节点i距离小于k[i]的点都会变黑，已经是黑的点保持为黑。问最少使用几次操作能把整棵树变黑。
输入描述:
第一行一个整数n (1 ≤ n ≤ 10^5) 接下来n-1行，每行一个整数，依次为2号点到n号点父亲的编号。 最后一行n个整数为k[i] (1 ≤ k[i] ≤ 10^5) 样例解释: 对节点3操作，导致节点2与节点3变黑 对节点4操作，导致节点4变黑 对节点1操作，导致节点1变黑
输出描述:
一个数表示最少操作次数
示例1
输入
4 1 2 1 1 2 2 1
输出
3
题意：给出一棵树，根节点编号为1，每个节点有一个权值ai表示从该节点向上距离不超过ai的点都可以被染色，求要使所有点被染色需要的最少操作次数
题解：容易想到dfs到叶子节点，叶子节点必须染色，然后在叶子结点以上被染过的点中找能染到的最小深度，以此向上染色操作次数最少，具体实现过程：递归地用dp[u]表示该节点或者该节点以下节点能染到的
最小深度，在已经被染色的点的尽头，也就是第一个未被染色的点A处ans+1，同时更新染色尽头为dp[A]即可，这里使用了数组pos记录染色尽头以便更新答案
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<vector> 6 #include<queue> 7 #include<map> 8 using namespace std; 9 //#define io_test 10 #define debug(x) cout<<x<<"####"<<endl; 11 typedef long long ll; 12 int rod[100005]; 13 const int inf=0x3f3f3f3f; 14 struct edge{ 15 int y; 16 int nex; 17 }e[100005]; 18 int head[100005],cnt,dep[100005],dp[100005],pos[100005]; 19 void adde(int x1,int y1){ 20 e[cnt].y=y1; 21 e[cnt].nex=head[x1]; 22 head[x1]=cnt++; 23 } 24 int cnt0=0; 25 void dfs(int u,int pre){ 26 dep[u]=dep[pre]+1; 27 dp[u]=dep[u]-rod[u]+1; 28 pos[u]=inf; 29 for(int i=head[u];i!=-1;i=e[i].nex){ 30 int v=e[i].y; 31 dfs(v,u); 32 dp[u]=min(dp[u],dp[v]); 33 pos[u]=min(pos[u],pos[v]); 34 } 35 if(pos[u]>dep[u]){ 36 cnt0++; 37 pos[u]=dp[u]; 38 } 39 } 40 int main() 41 { 42 #ifdef io_test 43 freopen("in.txt","r",stdin); 44 freopen("out.txt","w",stdout); 45 #endif // io_test 46 int n; 47 scanf("%d",&n); 48 memset(head,-1,sizeof(head)); 49 for(int i=2;i<=n;i++){ 50 int a; 51 scanf("%d",&a); 52 adde(a,i); 53 } 54 for(int i=1;i<=n;i++)scanf("%d",&rod[i]); 55 dep[0]=1; 56 dfs(1,0); 57 printf("%d ",cnt0); 58 return 0; 59 }
链接：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 ≤ n ≤ 500000, 1 ≤ s, x, y ≤ n。
题意：给一棵树，取一个点之后，就不能再取它的相邻点，求最多取多少点
题解：裸的树形dp，dp[u][0]表示不取u点，dp[u][1]表示取u点，很容易得到转移方程
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<vector> 6 #include<queue> 7 #include<map> 8 using namespace std; 9 //#define io_test 10 #define debug(x) cout<<x<<"####"<<endl; 11 typedef long long ll; 12 int head[500005],cnt; 13 struct edge{ 14 int y; 15 int nex; 16 }e[1000005]; 17 int dp[500005][2]; 18 void adde(int x1,int y1){ 19 e[cnt].y=y1; 20 e[cnt].nex=head[x1]; 21 head[x1]=cnt++; 22 } 23 void dfs(int u,int fa){ 24 int xx=0; 25 int yy=1; 26 // debug(u); 27 for(int i=head[u];i!=-1;i=e[i].nex){ 28 int v=e[i].y; 29 // debug(v); 30 if(v==fa)continue; 31 dfs(v,u); 32 xx+=max(dp[v][0],dp[v][1]); 33 yy+=dp[v][0]; 34 //dp[u][0]=max(dp[u][0],max(dp[v][]) 35 } 36 dp[u][0]=max(dp[u][0],xx); 37 dp[u][1]=max(dp[u][1],yy); 38 } 39 int main() 40 { 41 #ifdef io_test 42 freopen("in.txt","r",stdin); 43 freopen("out.txt","w",stdout); 44 #endif // io_test 45 int n,s; 46 scanf("%d%d",&n,&s); 47 memset(head,-1,sizeof(head)); 48 for(int i=1;i<n;i++){ 49 int a,b; 50 scanf("%d%d",&a,&b); 51 adde(a,b); 52 adde(b,a); 53 } 54 dfs(s,-1); 55 printf("%d ",dp[s][1]); 56 return 0; 57 58 }
链接：https://ac.nowcoder.com/acm/problem/19914
来源：牛客网
[CQOI2009]叶子的染色
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
给一棵m个结点的无根树，你可以选择一个度数大于1的结点作为根，然后给一些结点（根、内部结点和叶子均可）着以黑色或白色。你的着色方案应该保证根结点到每个叶子的简单路径上都至少包含一个有色结点（哪怕是这个叶子本身）。
对于每个叶结点u，定义c[u]为从根结点从U的简单路径上最后一个有色结点的颜色。给出每个c[u]的值，设计着色方案，使得着色结点的个数尽量少。
输入描述:
第一行包含两个正整数m, n，其中n是叶子的个数，m是结点总数。结点编号为1，2，…，m，其中编号1，2，… ，n是叶子。
以下n行每行一个0或1的整数（0表示黑色，1表示白色），依次为c[1]，c[2]，…，c[n]。
以下m-1行每行两个整数a，b（1 ≤ a < b ≤ m），表示结点a和b 有边相连。
输出描述:
仅一个数，即着色结点数的最小值。
示例1
输入
5 3 0 1 0 1 4 2 5 4 5 3 5
输出
2
题解：dp[u][0]表示u点染成0，dp[u][1]表示u点染成1，可得转移方程dp[u][0]=$sum_{i=0}^{g[u].size()}$(min(dp[g[u][i]][0],dp[g[u][i]][1]+1)),dp[u][1]=$sum_{i=0}^{g[u].size()}$(min(dp[g[u][i]][1],dp[g[u][i]][0]+1))
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<vector> 6 #include<queue> 7 #include<map> 8 using namespace std; 9 //#define io_test 10 #define debug(x) cout<<x<<"####"<<dp[x][0]<<"##"<<dp[x][1]<<endl; 11 typedef long long ll; 12 const int inf=0x3f3f3f3f; 13 int head[500005],cnt,a[500005],in[500005]; 14 struct edge{ 15 int y; 16 int nex; 17 }e[1000005]; 18 int dp[500005][2],n,m; 19 void adde(int x1,int y1){ 20 e[cnt].y=y1; 21 e[cnt].nex=head[x1]; 22 head[x1]=cnt++; 23 } 24 void dfs(int u,int fa){ 25 int flag=1; 26 // debug(u); 27 //dp[u][1]=dp[u][0]=inf; 28 for(int i=head[u];i!=-1;i=e[i].nex){ 29 int v=e[i].y; 30 // debug(v); 31 flag=0; 32 if(v==fa)continue; 33 dfs(v,u); 34 dp[u][1]+=min(dp[v][1],dp[v][0]+1); 35 dp[u][0]+=min(dp[v][0],dp[v][1]+1); 36 // debug(u); 37 // debug(v); 38 } 39 //debug(u); 40 if(u<=m){ 41 dp[u][a[u]]=0; 42 dp[u][a[u]^1]=inf; 43 } 44 } 45 int main() 46 { 47 #ifdef io_test 48 freopen("in.txt","r",stdin); 49 freopen("out.txt","w",stdout); 50 #endif // io_test 51 //int n,m; 52 scanf("%d%d",&n,&m); 53 memset(head,-1,sizeof(head)); 54 int s; 55 for(int i=1;i<=m;i++)scanf("%d",&a[i]); 56 for(int i=1;i<n;i++){ 57 int a1,b1; 58 scanf("%d%d",&a1,&b1); 59 adde(a1,b1); 60 adde(b1,a1); 61 in[a1]++; 62 in[b1]++; 63 if(in[a1]>1){ 64 s=a1; 65 } 66 if(in[b1]>1){ 67 s=b1; 68 } 69 } 70 //debug(s); 71 dfs(s,-1); 72 printf("%d ",min(dp[s][1],dp[s][0])+1); 73 return 0; 74 }