P3554 [POI2013]LUK-Triumphal arch

因为所求的值类似于一个覆盖范围，所以无法直接求解 用二分转化为判定性问题 然后就是树形$dp$了 可以看出B一定只会从根节点走到叶子结点，不会走回头路 （走回头路相当于自己啥也没干还让A多染了几次色） 设$f[i]$表示在$i$的子树中（不包括$i$）还需要染色的次数 转移就是求出$i$的子节点的$f$值总和，记为$sum$ 然后$f[i]=max(0,sum+d[i]-mid)$ $d[i]$表示$i$的度数（不包括它的父节点） 每一次二分都做一次dp 如果$f[1]==0$，则答案可行 关于数据范围：bzoj是3e5，luogu没给，但是1e5可以过 ~~我先在luogu做的交到bzoj还RE了一发~~ ``` #include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #define reg register using namespace std; const int N=3e5+5; struct node { int to,nxt; }edge[N<<1]; int n,num,head[N],f[N],mid; inline int read() { int x=0,w=1; char c=getchar(); while (!isdigit(c)&&c!='-') c=getchar(); if (c=='-') c=getchar(),w=-1; while (isdigit(c)) { x=(x<<1)+(x<<3)+c-'0'; c=getchar(); } return x*w; } inline void add_edge(int from,int to) { edge[++num]=(node){to,head[from]}; head[from]=num; } void dfs(int k,int fa) { int sum=0; for (reg int i=head[k];i;i=edge[i].nxt) { int v=edge[i].to; if (v==fa) continue; dfs(v,k); sum+=f[v]+1; } f[k]=max(sum-mid,0); } int main() { n=read(); if (n==1) {puts("0"); return 0;} for (reg int i=1;i<n;i++) { int x=read(),y=read(); add_edge(x,y); add_edge(y,x); } int l=1,r=n-1,ans=0; while (l<=r) { memset(f,0,sizeof(f)); mid=(l+r)>>1; dfs(1,0); if (!f[1]) ans=mid,r=mid-1; else l=mid+1; } printf("%d\n",ans); return 0; } ```