题意: 一开始有n个点 且每个点有其价值
有三个操作
1 选取路径 x y 并获得其价值
2 删除x的价值 也就是放弃x （如果x未选择就不用删除）
3 选取x及x的子树
每次询问都要输出获得的价值总和
三个操作都很简单
主要是是线段树有一点不一样 用前缀和可以解决 见代码
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) #define pb push_back #define lson l,m,pos<<1 #define rson m+1,r,pos<<1|1 #define inf 0x3f3f3f3f #define CLR(A,v) memset(A,v,sizeof A) typedef pair<int,int>pii; ////////////////////////////////// const int N=1e6+10; int t[N<<2],col[N<<2],n,m,node[N],w[N],sum[N],le[N],ri[N],a,b,c,pre[N]; void up(int pos) { t[pos]=t[pos<<1]+t[pos<<1|1]; } void build(int l,int r,int pos) { le[pos]=l;ri[pos]=r;col[pos]=0; if(l==r){t[pos]=0;return ; } int m=(l+r)>>1;build(lson);build(rson);up(pos); } void down(int pos) { if(col[pos]) { t[pos<<1]=sum[ri[pos<<1]]-sum[le[pos<<1]-1]; t[pos<<1|1]=sum[ri[pos<<1|1]]-sum[le[pos<<1|1]-1]; col[pos<<1]=col[pos<<1|1]=1; col[pos]=0; } } void upsum(int L,int R,int l,int r,int pos) { if(L<=l&&r<=R){t[pos]=sum[r]-sum[l-1];col[pos]=1;return; } int m=(l+r)>>1;down(pos); if(L<=m)upsum(L,R,lson); if(R>m)upsum(L,R,rson); up(pos); } void upnode(int x,int l,int r,int pos) { if(l==r){t[pos]=0;return;} int m=(l+r)>>1;down(pos); if(x<=m)upnode(x,lson); else upnode(x,rson); up(pos); } int head[N<<1],pos,id[N],dep[N],son[N],siz[N],top[N],cnt,fa[N]; struct Edge { int to,nex; }edge[N<<1]; void add(int a,int b) { edge[++pos]=(Edge){b,head[a]}; head[a]=pos; } void dfs1(int x,int f) { fa[x]=f;siz[x]=1;son[x]=0;dep[x]=dep[f]+1; for(int i=head[x];i;i=edge[i].nex) { int v=edge[i].to;if(v==f)continue; dfs1(v,x);siz[x]+=siz[v]; if(siz[son[x]]<siz[v])son[x]=v; } } void dfs2(int x,int topf) { id[x]=++cnt;w[cnt]=node[x];top[x]=topf;pre[cnt]=x; if(son[x])dfs2(son[x],topf); for(int i=head[x];i;i=edge[i].nex) { int v=edge[i].to; if(v==fa[x]||v==son[x])continue; dfs2(v,v); } } void UPsum(int x,int y) { while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]])swap(x,y); upsum(id[top[x]],id[x],1,n,1); x=fa[top[x]]; } if(dep[x]>dep[y])swap(x,y); upsum(id[x],id[y],1,n,1); } void init() { pos=cnt=0;CLR(head,0);dep[1]=son[0]=0;CLR(sum,0); } int main() { int cas;RI(cas); while(cas--) { RI(n);init(); rep(i,1,n)RI(node[i]); rep(i,1,n-1)RII(a,b),add(a,b),add(b,a); dfs1(1,1);dfs2(1,1);build(1,n,1); RI(m); sum[0]=0; rep(i,1,n)sum[i]=sum[i-1]+node[pre[i]]; while(m--) { RI(a); if(a==1)RII(b,c),UPsum(b,c); else if(a==2)RI(b),upnode(id[b],1,n,1); else RI(b),upsum(id[b],id[b]+siz[b]-1,1,n,1); printf("%d ",t[1]); } } return 0; }