P4183 [USACO18JAN] Cow at Large P

· · 题解

怎么题解区就没有一个不用容斥的 (2-du_i) 做法……

思路：

令 g_i 表示 i 到最近的叶子节点的距离。

考虑先求出到达子树内的叶子节点的最短距离：

void dfs1(ll u,ll fa){
    if(d[u]==1)
      g[u]=0;
    else
      g[u]=INF;
    for(auto v:E[u]){
        if(v==fa)
          continue;
        dfs1(v,u);
        g[u]=min(g[u],g[v]+1);
    }
}

然后 u 点还可以走到 fa_u，即可以令 g_u \gets \min(g_u,g_{fa_u}+1)：

void dfs2(ll u,ll fa){
    for(auto v:E[u]){
        if(v==fa)
          continue;
        g[v]=min(g[v],g[u]+1);
        dfs2(v,u);
    }
}

那么若一个点 i 可以拦截住从 u 出发的贝茜，当且仅当贝茜到达这个点的距离大于或等于这个点到达出口的最短路程，即 dis(i,u) \ge g_i。

注意到若点 i 可以拦截住贝茜，则点 i 子树内的点肯定也可以拦截贝茜，但是我们只需要 i 这一个点，那么需要满足 dis(i,u) \ge g_i,dis(fa_i,u) < g_{fa_i}。

即 ans_u=\sum_{i=1}^n[dis(i,u) \ge g_i][dis(fa_i,u)<g_{fa_i}]。

暴力求解是 O(N^2) 的，考虑进行优化。

注意到满足 dis(i,u) \ge g_i 的点肯定会构成 ans_u 棵子树。

因为一棵树中的一个长度为 m 的子树，子树内的点的度数和为 2m-1，即 \sum du_u = 2m - 1，那么可以得到 1 = \sum (2-du_u)。

则对于一棵满足 dis(i,u) \ge g_i 的子树，每个点的贡献为 (2-du_u)，那么这棵子树的贡献和就是 1。

现在问题转化为了求 ans_u = \sum_{i=1}^n [dis(i,u) \ge g_i] (2-du_i)，考虑点分治。

对于当前的分治重心即根 rt，rt 内两个不同儿子子树内的点 i,u，满足 dis(i,u) = dis(i,rt) + dis(u,rt)。

那么点分治需要处理三种贡献：

考虑令 dep_i 表示 i 到 rt 的距离，可以通过 dfs 一遍求出来。

对于 rt 中两个不同儿子子树的点之间的贡献，要满足 dis(i,u) \ge g_i 就是 dep_i + dep_u \ge g_i，即 dep_u \ge g_i - dep_i。

那么可以在 g_i-dep_i 位置上加入 2-du_i 的贡献，查询一个前缀和，很容易想到树状数组维护。

但是我们注意到对于点对 (i,u)，无法快速算 (u,i) 的贡献，考虑将 rt 儿子的枚举顺序翻转一遍，重新做一次即可。

对于 rt 到其子树的贡献，可以初始就在 g_{rt} - dep_{rt} = g_{rt} 处添加 2-du_{rt} 的贡献；这个的贡献在翻转重算的时候就不需要再算一次了。

对于 rt 子树内的点到 rt 的贡献，即贝茜从 rt 出发，那么一个点 i 能拦截需要满足 dis_i \ge g_i，即 g_i - dis_i \le 0，也用树状数组统计一下即可；这个的贡献在翻转重算的时候计算，因为不会将 rt 自己的贡献算进去。

注意到树状数组小标可能为负数，可以全体向右偏移 n。

注意每次计算的时候不可以能遍历整个树状数组清空，需要维护一个时间戳，这样时间复杂度才能保证。

总时间复杂度为 O(N \log^2 N)。

完整代码：

#include<bits/stdc++.h>
#define lowbit(x) x&(-x)
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
using namespace std;
typedef double db;
typedef long long ll;
const ll N=2e5+10,INF=1e9;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
      write(x/10);
    putchar(x%10+'0');
}
ll n,sum,Max,root,cnt,low;
ll a[N],b[N],ans[N],g[N],d[N],dep[N],siz[N],dis[N];
bool del[N];
vector<ll> E[N]; 
void add(ll u,ll v){
    d[u]++,d[v]++;
    E[u].push_back(v);
    E[v].push_back(u);
}
void Add(ll x,ll v){
    x+=n;
    for(int i=x;i<=2*n;i+=lowbit(i)){
        if(b[i]!=low){
            b[i]=low;
            a[i]=0;
        }
        a[i]+=v;
    }
}
ll query(ll x){
    x+=n;
    ll ans=0;
    for(int i=x;i;i-=lowbit(i)){
        if(b[i]!=low){
            b[i]=low;
            a[i]=0;
        }
        ans+=a[i];      
    }
    return ans;
}
void dfs1(ll u,ll fa){
    if(d[u]==1)
      g[u]=0;
    else
      g[u]=INF;
    for(auto v:E[u]){
        if(v==fa)
          continue;
        dfs1(v,u);
        g[u]=min(g[u],g[v]+1);
    }
}
void dfs2(ll u,ll fa){
    for(auto v:E[u]){
        if(v==fa)
          continue;
        g[v]=min(g[v],g[u]+1);
        dfs2(v,u);
    }
}
void getroot(ll u,ll fa){
    ll s=0;
    siz[u]=1;
    for(auto v:E[u]){
        if(v==fa||del[v])
          continue;
        getroot(v,u);
        siz[u]+=siz[v];
        s=max(s,siz[v]);
    }
    s=max(s,sum-siz[u]);
    if(s<Max){
        Max=s;
        root=u;
    }
}
void Get(ll u,ll s){
    root=0;
    sum=Max=s;
    getroot(u,0);
    getroot(root,0);
}
void getdis(ll u,ll fa){
    dis[++cnt]=u;
    for(auto v:E[u]){
        if(v==fa||del[v])
          continue;
        dep[v]=dep[u]+1;
        getdis(v,u);
    }
}
void Calc(ll u,bool f){
    ++low;
    dep[u]=0;
    if(f)
      Add(g[u]-dep[u],2-d[u]);
    for(auto v:E[u]){
        if(del[v])
          continue;
        cnt=0;
        dep[v]=1;
        getdis(v,u);
        for(int i=1;i<=cnt;i++)
          ans[dis[i]]+=query(dep[dis[i]]);
        for(int i=1;i<=cnt;i++)
          Add(g[dis[i]]-dep[dis[i]],2-d[dis[i]]);
    }
    if(!f)
      ans[u]+=query(0);
}
void calc(ll u){
    Calc(u,1);
    reverse(E[u].begin(),E[u].end());
    Calc(u,0);
}
void solve(ll u){
    calc(u);
    del[u]=1;
    for(auto v:E[u]){
        if(del[v])
          continue;
        Get(v,siz[v]);
        solve(root);
    } 
}
int main(){
    n=read();
    for(int u,v,i=1;i<n;i++){
        u=read(),v=read();
        add(u,v);
    }
    dfs1(1,0);
    dfs2(1,0);
    Get(1,n);
    solve(root);
    for(int i=1;i<=n;i++){
        write(ans[i]);
        putchar('\n');
    }
    return 0;
}