题目链接：
https://jzoj.net/senior/#contest/show/2529/1
题目：
题目背景：
尊者神高达作为一个萌新，在升级路上死亡无数次后被一只大黄叽带回了师门。他加入师门后发现有无穷无尽的师兄弟姐妹，这几天新副本开了，尊者神高达的师门作为一个 pve师门，于是他们决定组织一起去开荒。
题目描述：
师门可以看做以 1 为根的一棵树，师门中的每一个人都有一定的装备分数。一共会有 q 个事件。每个事件可能是一次开荒，也可能是因为开荒出了好装备而导致一个人的装分出现了变化。对于一次开荒，会有 k 个人组织，由于师门的号召力很强，所以所有在组织者中任意两个人简单路径上的人都会参加。
题目大意：
在树上给出多个点，每次询问包含这些点的最小连通块的点权之和，带修改
题解：
对于每一个询问，我们把点按照dfs序从小到大排序。画个图我们发现，假设当前点为第i个点，第i个点的贡献就是从第i个点到与第i-1个点的LCA上的路径上的点权和，但是不包括LCA的点权。为什么不包括LCA的点权呢？发现其实我们从第1个点到最终的LCA上的点权和（这个要算上最终的LCA）都没有计算，最后一起计算就是了
为什么是对的呢？我们考虑到排名靠后的点要么在上一个点的子树里，要么就是新开一个子树。对于前者我们发现公共LCA不上移，直接计算到上一个点的路径和就是了，而事实上上一个点和这个点的LCA就是上一个点。对于后者我们发现公共LCA发生上移，这在最终的答案被我们统计了进去。
#include<algorithm> #include<cstring> #include<iostream> #include<cstdio> #include<vector> using namespace std; typedef long long ll; const int N=1e5+15; int n,Q,tot,tim; int head[N],son[N],dep[N],fa[N][25],dfn[N],id[N],sz[N],a[N]; ll val[N],t[N]; struct EDGE { int to,nxt; }edge[N<<1]; inline ll read() { char ch=getchar(); ll s=0,f=1; while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9') {s=(s<<3)+(s<<1)+ch-'0';ch=getchar();} return s*f; } void link(int u,int v) { edge[++tot]=(EDGE){v,head[u]}; head[u]=tot; } void dfs(int x,int pre) { sz[x]=1;fa[x][0]=pre;dfn[x]=++tim;id[tim]=x; for (int i=1;i<25;i++) fa[x][i]=fa[fa[x][i-1]][i-1]; for (int i=head[x];i;i=edge[i].nxt) { int y=edge[i].to; if (y==pre) continue; dep[y]=dep[x]+1; dfs(y,x); sz[x]+=sz[y]; } } void add(int x,ll y) { while (x<=n) { t[x]+=y; x+=x&-x; } } ll sum(int x) { ll re=0; while (x) { re+=t[x]; x-=x&-x; } return re; } int lca(int x,int y) { if (dep[x]<dep[y]) swap(x,y); for (int i=24;i>=0;i--) if (dep[fa[x][i]]>=dep[y]) x=fa[x][i]; if (x==y) return x; for (int i=24;i>=0;i--) if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; return fa[x][0]; } bool cmp(int a,int b){return dfn[a]<dfn[b];} int main() { freopen("kaihuang.in","r",stdin); freopen("kaihuang.out","w",stdout); n=read();Q=read(); for (int i=1;i<=n;i++) val[i]=read(); for (int i=1,u,v;i<n;i++) { u=read();v=read(); link(u,v);link(v,u); } dep[1]=1;dfs(1,0); //for (int i=1;i<=n;i++) printf("%d ",sz[i]); //printf(" "); for (int i=1;i<=n;i++) { add(dfn[i],val[i]);add(dfn[i]+sz[i],-val[i]); } char op[5]; for (int i=1;i<=Q;i++) { scanf("%s",op); if (op[0]=='C') { int x=read();ll y=read(); add(dfn[x],-val[x]);add(dfn[x]+sz[x],val[x]); val[x]=y; add(dfn[x],y);add(dfn[x]+sz[x],-y); } if (op[0]=='Q') { int k=0; while (1) { int x=read(); if (!x) break; a[++k]=x; } sort(a+1,a+1+k,cmp); if (k==1) { printf("%lld ",val[a[1]]); continue; } ll re=sum(dfn[a[1]]);int LCA=a[1]; for (int i=2;i<=k;i++) { LCA=lca(LCA,a[i]); re+=sum(dfn[a[i]]); re-=sum(dfn[lca(a[i],a[i-1])]); } re-=sum(dfn[fa[LCA][0]]); printf("%lld ",re); } } return 0; }