首页 > 其他分享 >ABC337G Tree Inversion

ABC337G Tree Inversion

时间:2024-01-25 19:57:47浏览次数:22  
标签:Inversion 子树内 int Tree tr cnt pb ABC337G

思路

对于每个 \(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

相关文章

  • openGauss学习笔记-207 openGauss 数据库运维-常见故障定位案例-btree 索引故障情况下
    openGauss学习笔记-207openGauss数据库运维-常见故障定位案例-btree索引故障情况下应对策略207.1btree索引故障情况下应对策略207.1.1问题现象偶发索引丢失错误,报错如下。ERROR:index'xxxx_index'containsunexpectedzeropage或ERROR:index'pg_xxxx_index'cont......
  • 《Visual Tree Convolutional Neural Network in Image Classification》阅读笔记
    论文标题《VisualTreeConvolutionalNeuralNetworkinImageClassification》图像分类中的视觉树卷积神经网络作者YuntaoLiu、YongDou、RuochunJin和PengQiao来自国防科技大学并行和分布式处理国家实验室初读摘要问题:在图像分类领域,随着深度学习的快速发展,卷......
  • centos 离线安装tree命令
    在线安装tree命令:yum-yinstalltree 但是在线包总是下载失败:RepositoryepelislistedmorethanonceintheconfigurationRepositoryepel-debuginfoislistedmorethanonceintheconfigurationRepositoryepel-sourceislistedmorethanonceinthecon......
  • Electron 解决 connect ETIMEDOUT 或 sill idealTree buildDeps
    参考https://blog.csdn.net/Johanna51/article/details/123360477https://www.electronjs.org/zh/docs/latest/tutorial/installationhttps://cloud.tencent.com/developer/article/1781066环境环境版本说明Windows10nodev20.11.0npm10.2.4Windows......
  • CodeForces 1010F Tree
    洛谷传送门CF传送门educational的。另一道类似的题是[ABC269Ex]Antichain(但是我还没写)。考虑令\(b_u=a_u-\sum\limits_{v\inson_u}a_v\)。那么\(\sum\limits_{i=1}^nb_i=a_1=x\),且\(\foralli\in[1,n],b_i\ge0\)。所以最后连通块内有\(y\)个点,那......
  • 「笔记」dsu on tree
    目录写在前面引入树上启发式合并代码复杂度分析例题CF570DTreeRequestsCF600ELomsatgelralCF1709EXORTree写在最后写在前面高产似那啥。还以为这东西是啥科技呃呃,原来是能证明复杂度的乱搞。所以重链剖分就是动态dsu(精神错乱引入dsuontree,即树上启发式合并。启发......
  • 优美的暴力——树上启发式合并(dsu on tree)
    dsuontree前言在我认为,这个并不能说单独列出来成为一个算法,更恰当的说,是一种思想、技巧。反正挺简单的,也很有趣(谁会拒绝一个优美的暴力呢),所以写篇笔记记录一手。dsu是什么dsu一般指“disjointsetunion”,即并查集。那么dsuontree也就是指树上的合并和查询操作。但是......
  • Binary tree traversal-- beadth-first and depth-first【1月23日学习笔记】
    点击查看代码//Binarytreetraversal--beadth-firstanddepth-first#include<iostream>#include<queue>//STLusingnamespacestd;structnode{intdata;node*left,*right;};node*getnewnode(intx){node*temp=newnode;temp-&......
  • Binary tree traversal-- level-order traversal using queue【1月23日学习笔记】
    点击查看代码//Binarytreetraversal--level-ordertraversalusingqueue#include<iostream>#include<queue>//STLusingnamespacestd;structnode{intdata;node*left,*right;};node*getnewnode(intx){node*temp=newnode;t......
  • Find height of a binary tree【1月23日学习笔记】
    点击查看代码#include<iostream>usingnamespacestd;structNode{intdata;Node*left,*right;};Node*newNode(intx){Node*temp=newNode;temp->data=x;temp->left=temp->right=NULL;returntemp;}voidin......