AT_abc337_g 题解

_Ch1F4N_ · 2024-01-20 22:32:24 · 题解

最简单的一集。

考虑从小到大枚举 w 顺便加入所有的 v，偏序关系就已经没了，然后讨论 u,v 相对 w 的位置关系，如一个在子树内一个在子树外与在不同的子树内，无论如何都是一个子树或者全局刨去一个子树或者一个子树刨去一个子树内的 v 给类似的 u 做贡献，直接树状数组在 dfs 序上维护即可，时间复杂度 O(n \log n) 毫无卡常就过了。

#include<bits/stdc++.h>
#define lowbit(x) (x&(-x))
#define int long long
using namespace std;
const int maxn = 2e5+114;
int dfncnt,L[maxn],R[maxn],sz[maxn],n;
int p[maxn],answer[maxn];
//p 数组是点加区间查询 answer 数组是区间加点查询
void ins(int u){
    int pos=L[u];
    while(pos<=n) p[pos]++,pos+=lowbit(pos);
}
int pre(int x){
    int res=0;
    while(x>0) res+=p[x],x-=lowbit(x);
    return res;
}
int ask(int u){
    return pre(R[u])-pre(L[u]-1);
}
void add(int l,int r,int c){
    if(l>r) return ;
    r++;
    while(l<=n) answer[l]+=c,l+=lowbit(l);
    while(r<=n) answer[r]-=c,r+=lowbit(r);
}
int solve(int u){
    int pos=L[u];
    int res=0;
    while(pos>0) res+=answer[pos],pos-=lowbit(pos);
    return res;
}
int father[maxn];
vector<int> edge[maxn];
void dfs(int u,int fa){
    L[u]=++dfncnt;
    father[u]=fa;
    for(int v:edge[u]) if(v!=fa) dfs(v,u);
    R[u]=dfncnt;
}
signed main(){
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++){
        //将点 i 作为 w 加入，此前已经加入的点视为 v
        int w=i;
        add(1,L[w]-1,ask(w));
        add(R[w]+1,n,ask(w));
        add(L[w],R[w],ask(1)-ask(w));
        for(int u:edge[w]){
            if(u==father[w]) continue;
            add(L[u],R[u],ask(w)-ask(u));
        }
        add(L[w],L[w],ask(w));
        ins(w);
    }
    for(int i=1;i<=n;i++) cout<<solve(i)<<' ';
    return 0;
}