sol

考虑如何将恰好k个叶子变成求至少k个叶子.

我们可以强行枚举叶子, 即求

  • 至少包含S集合的点为叶子的方案数.

    这个可以将非S的集合做一遍\text{matrix-tree}定理

那么接下来就可以子集卷积了

或者…

考虑至少包含|S|个叶子节点的方案数记为f(x)

恰好包含|S|个叶子的方案数记为g(x)

很显然每个f(x) 中的方案是算多的.

f(x) = \sum_{i\ge x} \binom {i}{x} g(x)\\

那么二项式反演一下即可.

Code

#include <bits/stdc++.h>
using namespace std;
 
# define pb push_back
 
const int N = 1e6 + 5;
 
int n, u, v, son[N], sz[N], dep[N];
int d, cnt, ton[N], ans[N];
vector<int> g[N];
 
inline void Max(int &a, int b) {
    if(a < 0 || sz[a] < sz[b]) a = b;
}
inline void update(int u, int sy) {
    ton[dep[u]] += sy;
    if(ton[dep[u]] > cnt) {
        cnt = ton[dep[u]];
        d = dep[u];
    } else if(ton[dep[u]] == cnt)
        d = min(d, dep[u]);
}
void dfs1(int u, int fa = 0) {
    son[u] = -1;
    sz[u] = 1;
    dep[u] = dep[fa] + 1;
    for(auto v: g[u]) {
        if(v == fa) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        Max(son[u], v);
    }
}
void add(int u, int fa, int opt) {
    update(u, opt);
    for(auto v: g[u])
        if(v != fa) add(v, u, opt);
}
void dfs(int u, int fa, int opt) { // opt: whether clear it
    for(auto v: g[u]) {
        if(v == fa || v == son[u]) continue;
        dfs(v, u, 1);
    }
    if(son[u] > 0) dfs(son[u], u, 0);
    for(auto v: g[u]) {
        if(v == fa || v == son[u]) continue;
        add(v, u, 1);
    }
    update(u, 1);
    ans[u] = d;
    if(opt) {
        add(u, fa, -1);
        d = cnt = 0;
    }
}
int main() {
    scanf("%d", &n);
    for(int i = 1; i < n; ++i) {
        scanf("%d%d", &u, &v);
        g[v].pb(u), g[u].pb(v);
    }
    dfs1(1);
    dfs(1, 0, 1);
    for(int i = 1; i <= n; ++i)
        printf("%d\n", ans[i] - dep[i]);
    return 0;
}