思路
对于每个 \(1 \le i \le n\) 的 \(i\) 都要求答案,那我们考虑 dp,去思考如何转移 \(f_i\)。先不考虑全局,只考虑子树内的贡献,设 \(g_u\) 表示以 \(u\) 为根的子树内,对 \(u\) 来说满足条件的点对数。对于 \(u\) 的儿子 \(v\),对 \(v\) 来说合法那么对 \(u\) 来说也一定合法。因为从 \(v\) 开始的路径扩展到从 \(u\) 开始的路径只会让路径边长增加,自然也会包含那些点对,那么 \(g_u\) 就可以累加所有的 \(g_v\)。接下来就只有 \(w=u\) 的情况了(其他情况会包括在 \(g_v\) 中),问题就转化成了:求一棵子树内,小于点 \(u\) 的点有多少个。把每个节点按照他们的 dfs 序编号,子树内的编号就连续了,变成了一个序列问题,直接主席树就好了。
接下来就可以考虑换根了。从 \(u\) 转移到他的儿子 \(v\),可以先累加 \(f_u\) (全局的点对数)的贡献,但这样会把 \(w=u\),且他和 \(v\) 子树内的点配对的情况算进去,这实际是不合法的,因此减去 \(v\) 子树中 \(<u\) 的点的数量。同时还要加上 \(v\) 子树外的点与 \(w=v\) 配对的情况,这部分就整体减局部,用全局 \(<v\) 的点的数量减去 \(v\) 子树内 \(<v\) 的点的数量即可。
此题便做完了。
code
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int N=2e5+5;
int n;
int idx,id[N],node[N],sz[N];
ll f[N];
vector<int>e[N];
int root[N],cnt;
struct Tree{
int l,r;
int sum;
}tr[N<<5];
void build(int &p,int l,int r){
p=++cnt;
if(l==r)return;
int mid=l+r>>1;
build(tr[p].l,l,mid);
build(tr[p].r,mid+1,r);
}
int update(int p,int l,int r,int v){
++cnt;
tr[cnt]=tr[p];
tr[cnt].sum++;
p=cnt;
if(l==r)return p;
int mid=l+r>>1;
if(v<=mid)tr[p].l=update(tr[p].l,l,mid,v);
else tr[p].r=update(tr[p].r,mid+1,r,v);
return p;
}
int query(int pl,int pr,int l,int r,int v){
if(!v)return 0;
if(l==r)return tr[pr].sum-tr[pl].sum;
int mid=l+r>>1;
int res=0;
if(v<=mid)res+=query(tr[pl].l,tr[pr].l,l,mid,v);
else res+=tr[tr[pr].l].sum-tr[tr[pl].l].sum+query(tr[pl].r,tr[pr].r,mid+1,r,v);
return res;
}
void dfs1(int u,int fa){
id[u]=++idx;node[idx]=u;sz[u]=1;
for(auto v:e[u])if(v!=fa)dfs1(v,u),sz[u]+=sz[v];
}
void dfs(int u,int fa){
f[u]=query(root[id[u]-1],root[id[u]+sz[u]-1],1,n,u-1);//预处理出 g[u]
for(auto v:e[u]){
if(v==fa)continue;
dfs(v,u);
f[u]+=f[v];
}
}
void fds(int u,int fa){
for(auto v:e[u]){
if(v==fa)continue;
f[v]=f[u]-query(root[id[v]-1],root[id[v]+sz[v]-1],1,n,u-1)+query(root[0],root[n],1,n,v-1)-query(root[id[v]-1],root[id[v]+sz[v]-1],1,n,v-1);//换根
fds(v,u);
}
}
int main(){
cin>>n;
for(int i=1;i<n;++i){
int a,b;
cin>>a>>b;
e[a].pb(b);e[b].pb(a);
}
dfs1(1,0);
build(root[0],1,n);
for(int i=1;i<=n;++i)root[i]=update(root[i-1],1,n,node[i]);//主席树求区间小于某个数的个数
dfs(1,0);
fds(1,0);
for(int i=1;i<=n;++i)cout<<f[i]<<" ";
return 0;
}
标签:Inversion,子树内,int,Tree,tr,cnt,pb,ABC337G
From: https://www.cnblogs.com/sunsetlake/p/17988023