题目

对于每个叶结点u，定义c[u]为从u到根结点的简单路径上第一个有色结点的颜色。给出每个c[u]的值，设计着色方案，使得着色结点的个数尽量少。

---

分析

这道题可以用树形dp，$f[x][0/1]$表示x点不着色/着色的最小着色结点个数，
容易得到$f[x][0]=\sum min(f[son][0]-1,f[son][1])$
$f[x][1]=\sum min(f[son][0],f[son][1]-1)$
初始化时，对于每个叶子节点着色为1，不着色inf，而根节点初始化都是1。

---

代码

#include <cstdio>
#include <cctype>
#define min(a,b) (a<b)?a:b
using namespace std;
struct node{int y,next;}e[200001];
int n,m,ques[100001],ls[100001],f[200001][2];
int in(){int ans=0; char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=ans*10+c-48,c=getchar();return ans;
}
void dp(int x,int fa){if (x<=n) f[x][ques[x]]=1,f[x][ques[x]^1]=1<<23; else f[x][0]=f[x][1]=1;for (int i=ls[x];i;i=e[i].next){if (e[i].y==fa) continue;dp(e[i].y,x);f[x][0]+=min(f[e[i].y][0]-1,f[e[i].y][1]);f[x][1]+=min(f[e[i].y][0],f[e[i].y][1]-1);}
}
int main(){m=in(); n=in();for (int i=1;i<=n;i++) ques[i]=in();for (int i=1,x,y;i<m;i++){x=in(); y=in();e[i]=(node){y,ls[x]}; ls[x]=i;e[i+m]=(node){x,ls[y]}; ls[y]=i+m;}dp(m,0); return !printf("%d",min(f[m][0],f[m][1]));
}