树剖T了两个点
查看原帖
树剖T了两个点
117756
liuziyan楼主2020/7/31 08:27

有大佬帮我查查错嘛?

#include <bits/stdc++.h>
using namespace std;
const int N=3e4+10;
struct Node{
	int v,nxt;
}e[N*2];
int head[N],ne;
int n,u,v,q,x;
int w[N];
int dep[N],siz[N],fa[N],son[N],top[N],rank[N],dfn[N],cnt;
int max_ans,sum_ans;
struct Tree{
	int l,r,sum,mx;
}t[N<<2];
inline void add_edge(int u,int v) {
	e[ne].v=v;
	e[ne].nxt=head[u];
	head[u]=ne++;
}
inline int read() //快读 
{
	int x=0,f=1;
	char ch=getchar();
	while (!isdigit(ch)){
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (isdigit(ch)){
		x=x*10+ch-48;
		ch=getchar();
	}
	return x*f;
}
inline void pushup(int rt) {
	t[rt].sum = t[rt<<1].sum + t[rt<<1|1].sum;
	t[rt].mx = max(t[rt<<1].mx, t[rt<<1|1].mx);
}
void dfs1(int x){
	son[x]=-1;
	siz[x]=1;
	dep[x]=dep[fa[x]]+1;
	for (int i=head[x];i!=-1;i=e[i].nxt){
		int v=e[i].v;
		if (v==fa[x]) continue;
		fa[v]=x;
		dfs1(v);
		siz[x]+=siz[v];
		if (son[x]==-1 || siz[x]>siz[son[x]]){
			son[x]=v;
		}
	}
}
void dfs2(int x,int pre){
	top[x]=pre;
	dfn[x]=++cnt;
	rank[cnt]=x;
	if (son[x]==-1) return;
	dfs2(son[x],pre);
	for (int i=head[x];i!=-1;i=e[i].nxt){
		int v=e[i].v;
		if (v==fa[x] || v==son[x]) continue;
		dfs2(v,v);
	}
}
void build(int rt,int l,int r){
	t[rt].l=l;
	t[rt].r=r;
	t[rt].sum=t[rt].mx=0;
	if (l==r){
		t[rt].sum=t[rt].mx=w[rank[l]];
		return;
	}
	int mid=(l+r)>>1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
	pushup(rt);
}
void update(int rt,int pos,int val){
	if (t[rt].l==t[rt].r && t[rt].l==pos){
		t[rt].sum=val;
		t[rt].mx=val;
		return;
	}
	int mid=(t[rt].l+t[rt].r)>>1;
	if (pos<=mid){
		update(rt<<1,pos,val);
	}
	else{
		update(rt<<1|1,pos,val);
	}
	pushup(rt);
}
void qmax(int rt,int L,int R){
	if (L<=t[rt].l && t[rt].r<=R){
		max_ans=max(max_ans,t[rt].mx);
		return;
	}
	int mid=(t[rt].l+t[rt].r)>>1;
	if (L<=mid){
		qmax(rt<<1,L,R);
	}
	if (R>mid){
		qmax(rt<<1|1,L,R);
	}
}
void qsum(int rt,int L,int R){
	if (L<=t[rt].l && t[rt].r<=R){
		sum_ans+=t[rt].sum;
		return;
	}
	int mid=(t[rt].l+t[rt].r)>>1;
	if (L<=mid){
		qsum(rt<<1,L,R);
	}
	if (R>mid){
		qsum(rt<<1|1,L,R);
	}
}
inline void query(int flag,int x,int y){
	int tx=top[x],ty=top[y];
	while (tx!=ty){
		if (dep[tx]<dep[ty]){
			swap(tx,ty);
			swap(x,y);
		}
		if (flag==1){
			qmax(1,dfn[tx],dfn[x]);
		}
		else{
			qsum(1,dfn[tx],dfn[x]);
		}
		x=fa[tx];
		tx=top[x];
	}
	if (dep[x]>dep[y]) swap(x,y);
	if (flag==1){
		qmax(1,dfn[x],dfn[y]);
	}
	else{
		qsum(1,dfn[x],dfn[y]);
	}
}
int main(){
	n=read();
	memset(head,-1,sizeof(head));
	ne=0;
	for (int i=1;i<=n-1;i++){
		u=read();v=read();
		add_edge(u,v);
		add_edge(v,u);
	}
	for (int i=1;i<=n;i++){
		w[i]=read();
	}
	dfs1(1);
	cnt=0;
	dfs2(1,1);
	build(1,1,n);
	q=read();
	char s[10];
	while (q--){
		sum_ans=0;
		max_ans=-(1e9+7);
		scanf("%s",s);
		if (s[0]=='C'){
			u=read(),x=read();
			update(1,dfn[u],x);
		}
		else if (s[0]=='Q' && s[1]=='M'){
			u=read(),v=read();
			query(1,u,v);
			printf("%d\n",max_ans);
		}
		else{
			u=read(),v=read();
			query(2,u,v);
			printf("%d\n",sum_ans);
		}
	}
	return 0;
}
2020/7/31 08:27
加载中...