考虑二分答案。
肯定是对每个节点的儿子都要染色。
当时以为是所有节点的儿子数量的最多的。
后来发现前面如果有多余可以多给后面的。
设\(f[i]\)为\(i\)节点及子树的和标准操作的差。
那么\(f[i] = \sum_{(i \to v)}\ max(0,f[v]) + son[i] - k\)
考虑\(f[1]\)是否下于0即可。
#include<iostream>
#include<cstdio>
#define ll long long
#define N 300005
ll n;
struct P{
int to,next;
}e[N << 1];
ll cnt,head[N];
inline void add(int x,int y){
e[++cnt].to = y;
e[cnt].next = head[x];
head[x] = cnt;
}
ll son[N];
inline void dfs(int u,int f){
for(int i = head[u];i;i = e[i].next){
int v = e[i].to;
if(v == f)continue;
son[u] ++ ;
dfs(v,u);
}
}
ll f[N];
ll k;
inline void dfn(int u,int fa){
f[u] = son[u] - k;
for(int i = head[u];i;i = e[i].next){
int v = e[i].to;
if(v == fa)continue;
dfn(v,u);
f[u] += std::max((ll)0,f[v]);
}
}
inline bool check(ll x){
k = x;
for(int i = 1;i <= n;++i)
f[i] = 0;
dfn(1,0);
return (f[1] <= 0);
}
#define mid ((l + r) >> 1)
int main(){
scanf("%lld",&n);
for(int i = 1;i < n;++i){
ll x,y;
scanf("%lld%lld",&x,&y);
add(x,y);
add(y,x);
}
dfs(1,0);
ll l = 0,r = n;
while(l + 1 < r){
if(check(mid))
r = mid;
else
l = mid;
}
r ++ ;
while(check(r - 1))
r = r - 1;
std::cout<<r<<std::endl;
}