树剖 0pts,过样例
查看原帖
树剖 0pts,过样例
1065071
Atserckcn楼主2024/12/29 10:37
#include<bits/stdc++.h>
using namespace std;
#define ljl long long
#define lc (p<<1)
#define rc (p<<1|1)
const ljl N=1e5+5;
char ch;ljl u,v,d;
ljl head[N],n,tot,q,cnt_e;
ljl fa[N],rnk[N],tp[N],son[N],siz[N],dep[N],dfn[N];
struct E{
	ljl to,pre;
}e[N<<1];
struct TREE{
	ljl l,r,sum,lz;
}tree[N*4];
//--------------------------------segment tree 
void build(ljl l,ljl r,ljl p)
{
	tree[p].l=l;
	tree[p].r=r;
	if(l==r)
		return;
	ljl mid=l+r>>1;
	build(l,mid,lc);
	build(mid+1,r,rc);
	return;
}
ljl getlen(ljl p)
{
	return tree[p].r-tree[p].l+1;
}
void pushdown(ljl p)
{
	if(!tree[p].lz) return;
	tree[lc].lz+=tree[p].lz;
	tree[lc].sum+=(getlen(lc))*tree[p].lz;
	tree[rc].lz+=tree[p].lz;
	tree[rc].sum+=(getlen(rc))*tree[p].lz;
	tree[p].lz=0;
	return;
}
void pushup(ljl p)
{
	tree[p].sum=tree[lc].sum+tree[rc].sum;
	return;
}
void addsum(ljl l,ljl r,ljl c,ljl p)
{
	if(l>tree[p].l&&r<tree[p].r)return;
	if(l<=tree[p].l&&r>=tree[p].r)
	{
		tree[p].lz+=c;
		tree[p].sum+=(getlen(p))*c;
		pushdown(p);return;
	}
	ljl mid=tree[p].l+tree[p].r>>1;
	if(l<=mid)
		addsum(l,r,c,lc);
	if(r>mid)
		addsum(l,r,c,rc);
	pushup(p);
	return;
}
ljl query(ljl l,ljl r,ljl p)
{
	if(l<=tree[p].l&&r>=tree[p].r)
		return tree[p].sum;
	pushdown(p);
	ljl mid=tree[p].l+tree[p].r>>1;
	ljl sum=0;
	if(l<=mid)
		sum+=query(l,r,lc);
	if(r>mid)
		sum+=query(l,r,rc);
	return sum;	
}
void linkaddsum(ljl x,ljl y,ljl val)
{
	ljl tx=tp[x],ty=tp[y];
	while(tx!=ty)
	{
		if(dep[tx]<dep[ty])
		{
			swap(x,y);swap(tx,ty);
		}
		addsum(dfn[x],dfn[y],val,1);
		x=fa[tx];
		tx=tp[x];
	}
	if(dep[x]>dep[y])
		swap(x,y);
	addsum(dfn[x],dfn[y],val,1);return;
}
ljl linkquery(ljl x,ljl y)
{
	ljl sum=0;
	ljl tx=tp[x],ty=tp[y];
	while(tx!=ty)
	{
		if(dep[tx]<dep[ty])
		{
			swap(tx,ty);swap(x,y);
		}
		sum+=query(dfn[tx],dfn[ty],1);
		x=fa[tx];
		tx=tp[x];
	}
	if(dep[x]>dep[y])
		swap(x,y);
	sum+=query(dfn[x],dfn[y],1);
	return sum;
}
//------------------------------segment tree
void add(ljl from,ljl to)
{
	e[++cnt_e].to=to;
	e[cnt_e].pre=head[from];
	head[from]=cnt_e;		
	return;
}
void dfs1(ljl u)
{
	dep[u]=dep[fa[u]]+1;
	siz[u]=1;
	son[u]=-1;
	for(ljl i=head[u];i;i=e[i].pre)
	{
		ljl v=e[i].to;
		if(v==fa[u]) continue;
		fa[v]=u;
		dfs1(v);
		siz[u]+=siz[v];
		if(son[u]==-1||siz[v]>siz[son[u]])
			son[u]=v;
	}
	return;
}
void dfs2(ljl u,ljl t)
{
	tp[u]=t;
	dfn[u]=++tot;
	rnk[dfn[u]]=u;
	if(son[u]==-1) return;
	dfs2(son[u],t);
	for(ljl i=head[u];i;i=e[i].pre)
	{
		ljl v=e[i].to;
		if(v==fa[u]||v==son[u]) continue;
		dfs2(v,v);
	}
	return;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(ljl i=1;i<n;++i)
	{
		cin>>u>>v;++u,++v;
		add(u,v);add(v,u);
	}
	dfs1(1);dfs2(1,1);
	build(1,n,1);
	cin>>q;
	while(q--)
	{
		cin>>ch;
		if(ch=='A')
		{
			cin>>u>>v>>d;++u,++v;
			linkaddsum(u,v,d);
		}
		else
		{
			cin>>u;++u;
			ljl tx=dfn[u],ty=dfn[u]+siz[u]-1;
			cout<<query(tx,ty,1)<<'\n';
		}
	}
	return 0;
}
2024/12/29 10:37
加载中...