首页 > 其他分享 >题解 [ABC133F] Colorful Tree

题解 [ABC133F] Colorful Tree

时间:2022-12-18 18:45:21浏览次数:72  
标签:dist int 题解 top Tree fa ABC133F include

原题链接

考虑正常的 \(u\) 和 \(v\) 之间的距离怎么去求:我们可以维护每个值到根的距离 \(dist_i\) ,然后通过计算 \(dist_u+dist_v-2 \times dist_{lca}\) 得到,这里就不过多赘述。

考虑本题,我们发现只要能够求出改变后的 \(dist_i\) 的值即可,不妨利用主席树维护每个点 \(i\) 到根节点 \(1\) 的每种颜色的出现次数 \(cnt\) 以及权值和 \(sum\) ,那么此时真正的 \(dist'_i=dist_i-sum+cnt \times y\) 。

而主席树的每个点的权值可以继承其父亲的权值。时空复杂度均为 \(O(N \log N)\) 。

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,q,x,y,z,w;
struct node{
	int nxt;int to;int dist;int col;
}e[N*2];
int head[N],tot;
struct Chair{
	int ls;int rs;int sum;int cnt;
}Tree[N*32];
int root[N],Tcnt;

int fa[N],dep[N],sz[N],hson[N],top[N];
int val[N],col[N],dist[N];
/*这里使用了树剖求lca*/

inline void read(int &x) 
{
	int f=1;char c;
	for(x=0,c=getchar();c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48); x*=f;
} 
inline int mn(int _x,int _y){return _x<_y?_x:_y;}
inline int mx(int _x,int _y){return _x>_y?_x:_y;}
inline int ab(int _x){return _x<0?-_x:_x;}
inline void add(int from,int to,int col,int dist)
{
	e[++tot].to=to;
	e[tot].dist=dist;e[tot].col=col;
	e[tot].nxt=head[from];
	head[from]=tot;
}

inline int New(int x)
{
	++Tcnt;
	Tree[Tcnt]=Tree[x];
	return Tcnt;
}
inline int update(int x,int l,int r,int pos,int v)
{
	x=New(x);Tree[x].sum+=v;Tree[x].cnt++;
	if(l==r) return x;
	int mid=l+r>>1;
	if(pos<=mid) Tree[x].ls=update(Tree[x].ls,l,mid,pos,v);
	if(pos>mid) Tree[x].rs=update(Tree[x].rs,mid+1,r,pos,v);
	return x;
}
inline pair<int,int> query(int x,int l,int r,int pos)
{
	if(l==r) return make_pair(Tree[x].sum,Tree[x].cnt);
	int mid=l+r>>1;
	if(pos<=mid) return query(Tree[x].ls,l,mid,pos);
	if(pos>mid) return query(Tree[x].rs,mid+1,r,pos);
}
/*主席树的修改与查询*/
inline void dfs1(int x)
{
	sz[x]=1;
	for(int i=head[x];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==fa[x]) continue;
		fa[v]=x;dep[v]=dep[x]+1;
		val[v]=e[i].dist;col[v]=e[i].col;
		dist[v]=dist[x]+e[i].dist;
		dfs1(v);
		sz[x]+=sz[v];
		if(sz[v]>sz[hson[x]]) hson[x]=v;
	}
	return ;
}
inline void dfs2(int x,int tp)
{
	top[x]=tp;
	if(x!=1) root[x]=update(root[fa[x]],1,n,col[x],val[x]);
    /*如果不是根节点1就要继承父亲并且加入自己的值*/
	if(hson[x]) dfs2(hson[x],tp);
	for(int i=head[x];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==fa[x]||v==hson[x]) continue;
		dfs2(v,v);
	}	
}
inline int lca(int u,int v)
{
	while(top[u]!=top[v])
	{
		if(dep[top[u]]>dep[top[v]]) u=fa[top[u]];
		else v=fa[top[v]];
	}
	if(dep[u]<dep[v]) return u;
	else return v;
}


inline int getd(int x,int z,int w)
{
	pair<int,int> tmp=query(root[x],1,n,z);
	return dist[x]-tmp.first+w*tmp.second;//计算改变后的权值
}
int main()
{
	read(n);read(q);
	for(int i=1;i<n;i++)
	{
		read(x);read(y);read(z);read(w);
		add(x,y,z,w);add(y,x,z,w);
	}
	dep[1]=1;dfs1(1);dfs2(1,1);
	while(q--)
	{
		read(z);read(w);read(x);read(y);
		/这里注意读入的顺序 x,y才是查询的节点*/
		int lc=lca(x,y);
		printf("%d\n",getd(x,z,w)+getd(y,z,w)-2*getd(lc,z,w));
	}
	return 0;	
}  

同步发表于洛谷blog

标签:dist,int,题解,top,Tree,fa,ABC133F,include
From: https://www.cnblogs.com/infinite-nebula/p/16990748.html

相关文章

  • GuiLite 学习笔记(一) Mainloop与ViewTree
    以GuiLiteSamples中的HelloSlide为例,剖析一下GuiLite的设计思路和刷新机制;首先是main.cpp;可以分成3部分:1、根据fbmode拿到对应的phy_fb,后续的绘制都在这个fb上执行......
  • IDEA中Maven项目 子项目中缺少parent标签及无web框架问题解决
    Question在maven项目中,创建的子模块的pom中没有标签,但父模块中有,造成运行时提示版本源过低原因:maven的settings.xml中默认jdk版本过低解决方法:在maven中指定jdk版本,找到......
  • [ABC282D] Make Bipartite 2 题解
    题目描述给定一个无向简单图\(G\),统计有多少个点对\((u,v)\)满足:\(u,v\)之间没有边直接连接:\((u,v)\notin\textE\)连接\((u,v)\)后\(G\)是二分图......
  • 题解 CF1762E【Tree Sum】
    problem根据prufer引理,有标号的无根树的种类是\(n^{n-2}\)。对于一棵n个节点的带权无根树,边权总是+1或者-1。那么总共有\(n^{n-2}*2^{n-1}\)种树。其......
  • 题解 CF1109D【Sasha and Interesting Fact from Graph Theory】
    problem你尤其钟情\(a,b\)这两个数。对于一棵N个节点的树,已知所有边的长度都在\([1,m]\)之间,如果节点\(a\)和\(b\)的距离恰好为\(m\),那么你认为这棵树很好看......
  • 题解 AGC059C【Guessing Permutation for as Long as Possible】
    problem小明有一个隐藏的排列\(p\),小红想要猜出来。现在允许小红提问,每次提问的形式是\(a_i\)和\(b_i\),然后小明会告诉小红谁大谁小。小红是个老实的人,她的询问顺序......
  • 题解 SS221112B【Y】
    problem\(2n\)个有顺序的整数,每个数在\([0,m]\)内随机独立均匀生成,求前一半的和大于后一半的和的方案数。\(T,n,m\leq2000\)。solution0总方案数是明晰的:\(S=(m+1)......
  • 洛谷P3224 [HNOI2012]永无乡 题解 splay tree 启发式合并
    题目链接:https://www.luogu.com.cn/problem/P3224主要知识点是:树上启发式合并,即每次合并将小的树里面的每个点合并大大的树里面,时间复杂度\(O(n\log^2n)\)。同时需要......
  • java跨域问题解决
    问题描述:在使用前后端分离的情况下,前端访问后端时会出现跨域问题解决方式:1.设置跨域1)、单个控制器方法CORS注解在单个方法中加入注解@CrossOrigin。2)、整个控制器......
  • 题解 SP10264 METEORS - Meteors
    整体二分经典题,所以我们用分块解决Solution和整体二分类似,我们把\(k\)次操作分成\(\sqrtk\)块,每一块一起考虑。对于区间加,可以转化为差分,那么在每个块一起作差分后......