一道不错相对简单的题目。

Solution

很大胆的想法。考虑以子树dp，然后一条链大力拉下来枚举链底部求贡献。

那么对于每棵子树求最优的链底。

用线段树维护。考虑点上移，链底贡献的变化量。

重链贡献中有 $\log$ 的存在，但我们发现每个链底及其每棵子树对重链贡献的变化次数不会超过 $\log$ 次，因此复杂度是 $O(n\log^2 n)$ 的。

Code

// Code by ajcxsu
// Problem: new year duck

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=1e5+10, OP=19;
int gup[OP][N];
int h[N], to[N<<1], nexp[N<<1], p=1;
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++; }
int siz[N], dl[N], dr[N], idx;
void dfs(int x, int fr) {
    siz[x]=1, dl[x]=++idx;
    for(int u=h[x];u;u=nexp[u])
        if(to[u]!=fr) dfs(to[u], x), siz[x]+=siz[to[u]], gup[0][to[u]]=x;
    dr[x]=idx;
}

vector<int> add[N];
#define ls x<<1
#define rs x<<1|1
ll mi[N<<2], t[N<<2];
void pud(int x) {
    if(!t[x]) return;
    ll v=t[x];
    mi[ls]+=v, mi[rs]+=v, t[ls]+=v, t[rs]+=v; t[x]=0;
}
void updata(int x, int l, int r, int xl, int xr, ll v) {
    if(xl<=l && r<=xr) { mi[x]+=v, t[x]+=v; return; }
    pud(x); int mid=(l+r)>>1;
    if(xl<=mid) updata(ls, l, mid, xl, xr, v);
    if(xr>mid) updata(rs, mid+1, r, xl, xr, v);
    mi[x]=min(mi[ls], mi[rs]);
}
ll query(int x, int l, int r, int xl, int xr) {
    if(xl<=l && r<=xr) return mi[x];
    pud(x); int mid=(l+r)>>1; ll ret=1ll<<60;
    if(xl<=mid) ret=min(ret, query(ls, l, mid, xl, xr));
    if(xr>mid) ret=min(ret, query(rs, mid+1, r, xl, xr));
    return ret;
}
ll f[N]; int n;
void addv(int x) {
    int fa=gup[0][x];
    updata(1, 1, n, dl[x], dr[x], siz[x]);
    for(int u=h[x];u;u=nexp[u])
        if(to[u]!=fa) updata(1, 1, n, dl[to[u]], dr[to[u]], -siz[to[u]]);
}
void dfs2(int x, int fr) {
    ll tot=0;
    for(int u=h[x];u;u=nexp[u])
        if(to[u]!=fr) {
            dfs2(to[u], x);
            tot+=f[to[u]]+siz[to[u]];
        }
    for(int u=h[x];u;u=nexp[u]) if(to[u]!=fr) {
        updata(1, 1, n, dl[to[u]], dr[to[u]], tot-f[to[u]]-siz[to[u]]);
        addv(to[u]);
    }
    updata(1, 1, n, dl[x], dl[x], tot);
    for(int y:add[x]) addv(y);
    f[x]=dl[x]==dr[x]?0:query(1, 1, n, dl[x], dr[x]);
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int u, v;
    cin>>n;
    for(int i=0; i<n-1; i++) cin>>u>>v, ins(u, v), ins(v, u);
    dfs(1, 0);
    for(int j=1; j<OP; j++)
        for(int i=1; i<=n; i++)
            gup[j][i]=gup[j-1][gup[j-1][i]];
    for(int j=0; j<OP; j++)
        for(int i=1; i<=n; i++)
            if(gup[0][gup[j][i]]) add[gup[0][gup[j][i]]].push_back(i);
    dfs2(1, 0);
    cout<<f[1]<<endl;
    return 0;
}