萌新求助为何CE
  • 板块学术版
  • 楼主wolf_moon
  • 当前回复5
  • 已保存回复5
  • 发布时间2021/7/23 17:33
  • 上次更新2023/11/4 13:32:55
查看原帖
萌新求助为何CE
446229
wolf_moon楼主2021/7/23 17:33
#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define pb push_back
using namespace std;
const int N=1e5+5;vi v[N];
int n,m,q,mx[N],dep[N],top[N],dfn[N],nfd[N],sz[N],Fa[N];
int dfs(int now,int fa)
{
	dep[now]=dep[fa]+1;
	sz[now]=1;Fa[now]=fa;
	int num=n;
	for(int i=0;i<v[now].size();i++)
	{
		int to=v[now][i];
		if(to!=fa)
		{
			sz[now]+=sz[to]=dfs(to,now);
			if(num<sz[to]){
				num=sz[to];
				mx[now]=to;
			}
		}
	}
	return sz[now];
}
void heavy_light(int now,int fa)
{
	dfn[++m]=now;
	nfd[m]=now;
	if(mx[now]!=n)top[mx[now]]=top[now],heavy_light(mx[now],now);
	for(int i=0;i<v[now].size();i++)
	{
		int to=v[now][i];
		if(to!=now&&to!=mx[now])
			top[to]=to,heavy_light(to,now);
	}
	return;
}
struct segmentree{
	ll tree[N*8],lazy[N*8];
	void pushdown(int id)
	{
		if(lazy[id])
		{
			lazy[id<<1]+=lazy[id];
			lazy[id<<1|1]+=lazy[id];
			tree[id<<1]+=lazy[id];
			tree[id<<1]+=lazy[id];
			lazy[id]=0;
		}
		return;
	}
	void update(int l,int r,int x,int y,ll add,int id)
	{
		pushdown(id);
		if(x<=l&&r<=y)
		{
			tree[id]+=add;
			lazy[id]+=add;
			return;
		}
		int mid=(l+r)>>1;
		if(x<=mid)update(l,mid,x,y,add,id<<1);
		if(mid<y)update(mid+1,r,x,y,add,id<<1|1);
		return;
	}
	ll query(int l,int r,int p,int id)
	{
		pushdown(id);
		if(l==r)return tree[id];
		int mid=(l+r)>>1;
		if(mid>=p)return query(l,mid,p,id<<1);
		else return query(mid+1,r,p,id<<1|1);
	}
}t[4];
int LCA(int x,int y)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		x=Fa[top[x]];
	}
	if(dep[x]>dep[y])return y;
	else return x;
}
void addlian(int x,int y,ll add1,ll add2)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		t[0].update(1,n,dfn[top[x]],dfn[x],add1,1);
		t[1].update(1,n,dfn[top[x]],dfn[x],add2,1);
		t[2].update(1,n,dfn[top[x]],dfn[x],1,1);
		x=Fa[top[x]];
	}
	if(dep[x]<dep[y])swap(x,y);
	t[0].update(1,n,dfn[y],dfn[x],add1,1);
	t[1].update(1,n,dfn[y],dfn[x],add2,1);
	t[2].update(1,n,dfn[y],dfn[x],1,1);
	return;
}
int main()
{
	cin>>n;
	for(int i=0;i<n-1;i++)
	{
		int a,b;
		cin>>a>>b;
		a--,b--;
		v[a].pb(b);
		v[b].pb(a);
	}
	dfs(0,0);
	heavy_light(0,0);
	cin>>q;
	while(q--)
	{
		int t,a,b;
		cin>>t>>a;
		a--;
		if(t==1){
			cin>>b;
			b--;
			int lca=LCA(a,b);
			int len=dep[lca]-dep[a]+1;
			addlian(a,lca,-dep[a]+1,2ll*(-dep[a]+1));
			addlian(lca,b,len-dep[lca],len-dep[lca]);
//		
			t[0].update(1,n,dfn[lca],dfn[lca],dep[lca]-len,1);
			t[1].update(1,n,dfn[lca],dfn[lca],dep[lca]-len,1);
			t[2].update(1,n,dfn[lca],dfn[lca],-1,1);
			//Minuslen
		}else{
			ll ans=t[0].query(1,n,dfn[a],dfn[a],1);
			ans+=t[1].query(1,n,dfn[a],dfn[a],1)*dep[a];
			ans+=t[2].query(1,n,dfn[a],dfn[a],1)*dep[a]*dep[a];
		}
	}
	return 0;
}
2021/7/23 17:33
加载中...