不难发现，操作1可以看作如下操作：对于删去$a_{1},a_{2},...,a_{k}$后的每一个连通块（的点集）$V$，令$forall xin V,x$的收益加上$s$（其中$s=sum_{xin V}c_{x}$）
考虑建立类似于虚树的东西，即将每一个$a_{i}$连到第一个在$a_{i}$中的祖先，接下来遍历这棵新树（森林），对每一个节点枚举其在原树上的所有儿子，考虑该儿子的子树，分类讨论：
1.若这棵子树中没有$a_{i}$中的点，直接暴力修改（对dfs序维护线段树）
2.若这棵子树中有$a_{i}$中的点，找到还是其儿子的点（同时在其该子树中），将这些子树的dfs区间在整个区间中删掉，即将整个区间划分为若干段分别查询后求和并（分别）修改
关于如何建立前者的虚树，可以将所有节点子树对应的dfs区间排序后遍历一遍，或者也可以建立虚树之后再删除不在$a_{i}$中的点，时间复杂度均为$o(klog n)$
但是，这样的操作次数（指对线段树）并不是$o(k)$，瓶颈是在于第1类（第2类虽然看似复杂但仔细分析不难发现其是$o(k)$的），考虑如何处理：
先树链剖分预处理，并找到所有第2类中的儿子和重儿子，用之前的方式处理（这里只有$o(k)$次），并在该节点上打一个修改标记，查询时$v$到根路径上根据重链顶端的父亲的标记对该重链顶端子树修改
（为了方便，可以将第2类中的轻儿子再减去子树和）
另外，还有一些细节问题：
1.需要去掉自己与自己贸易的情况，可以通过对这$a_{i}$个点的收益补上$c_{a_{i}}$，并再在操作2时将此时的答案额外减去$mc_{v}$即可（其中$m$为之前操作1的次数），显然这容易维护
2.如果1不在$a_{i}$中，实际上忽略了最外部的连通块（严格来说即包含1的连通块），可以通过建边$(0,1)$并将0强制加入$a_{i}$中解决（或特判）
综上，总复杂度为$o((q+sum k)log n)$，可以通过
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 200005 4 #define ll long long 5 #define fi first 6 #define se second 7 #define L (k<<1) 8 #define R (L+1) 9 #define mid (l+r>>1) 10 struct Edge{ 11 int nex,to; 12 }edge[N<<1]; 13 int E,t,n,m,q,p,x,y,head[N],c[N],sz[N],mx[N],dep[N],fa[N][20],dfn[N],idfn[N],top[N],st[N],tag[N]; 14 ll sum[N],f[N]; 15 pair<int,int>a[N]; 16 vector<int>v[N]; 17 int lowbit(int k){ 18 return (k&(-k)); 19 } 20 ll get_sum(int k){ 21 return sum[dfn[k]+sz[k]-1]-sum[dfn[k]-1]; 22 } 23 void add(int x,int y){ 24 edge[E].nex=head[x]; 25 edge[E].to=y; 26 head[x]=E++; 27 } 28 int get_son(int x,int y){ 29 for(int i=19;i>=0;i--) 30 if (dep[fa[x][i]]>dep[y])x=fa[x][i]; 31 return x; 32 } 33 void dfs1(int k,int f,int s){ 34 sz[k]=1,mx[k]=0,dep[k]=s,fa[k][0]=f; 35 for(int i=1;i<20;i++)fa[k][i]=fa[fa[k][i-1]][i-1]; 36 for(int i=head[k];i!=-1;i=edge[i].nex) 37 if (edge[i].to!=f){ 38 dfs1(edge[i].to,k,s+1); 39 sz[k]+=sz[edge[i].to]; 40 if ((!mx[k])||(sz[mx[k]]<sz[edge[i].to]))mx[k]=edge[i].to; 41 } 42 } 43 void dfs2(int k,int f,int t){ 44 dfn[k]=++dfn[0],idfn[dfn[0]]=k,top[k]=t; 45 if (mx[k])dfs2(mx[k],k,t); 46 for(int i=head[k];i!=-1;i=edge[i].nex) 47 if ((edge[i].to!=f)&&(edge[i].to!=mx[k]))dfs2(edge[i].to,k,edge[i].to); 48 } 49 void update(int k,ll x){ 50 while (k<=n){ 51 f[k]+=x; 52 k+=lowbit(k); 53 } 54 } 55 void update(int x,int y,ll z){ 56 update(x,z); 57 if (y<n)update(y+1,-z); 58 } 59 void dfs(int k){ 60 if (k)tag[k]++; 61 bool flag=0; 62 for(int i=0,j=0;i<v[k].size();i=j){ 63 int son=get_son(v[k][i],k); 64 ll s=get_sum(son); 65 while ((j<v[k].size())&&(get_son(v[k][j],k)==son))s-=get_sum(v[k][j++]); 66 update(dfn[son],dfn[son]+sz[son]-1,s); 67 for(int t=i;t<j;t++)update(dfn[v[k][t]],dfn[v[k][t]]+sz[v[k][t]]-1,-s); 68 if (son==mx[k])flag=1; 69 else update(dfn[son],dfn[son]+sz[son]-1,-get_sum(son)); 70 } 71 if ((!flag)&&(mx[k]))update(dfn[mx[k]],dfn[mx[k]]+sz[mx[k]]-1,get_sum(mx[k])); 72 for(int i=0;i<v[k].size();i++)dfs(v[k][i]); 73 v[k].clear(); 74 } 75 ll query(int k){ 76 ll ans=0; 77 for(int i=dfn[k];i;i-=lowbit(i))ans+=f[i]; 78 ans-=(ll)m*c[k]; 79 while (k){ 80 ans+=tag[fa[top[k]][0]]*get_sum(top[k]); 81 k=fa[top[k]][0]; 82 } 83 return ans; 84 } 85 int main(){ 86 scanf("%d",&t); 87 while (t--){ 88 scanf("%d%d",&n,&q); 89 E=m=dfn[0]=0; 90 memset(head,-1,sizeof(head)); 91 memset(tag,0,sizeof(tag)); 92 memset(f,0,sizeof(f)); 93 for(int i=1;i<n;i++){ 94 scanf("%d%d",&x,&y); 95 add(x,y),add(y,x); 96 } 97 dfs1(1,0,1),dfs2(1,0,1); 98 dfn[0]=mx[0]=1,sz[0]=n; 99 for(int i=1;i<=n;i++)scanf("%d",&c[i]); 100 for(int i=1;i<=n;i++)sum[i]=sum[i-1]+c[idfn[i]]; 101 for(int i=1;i<=q;i++){ 102 scanf("%d%d",&p,&x); 103 if (p==1){ 104 m++; 105 for(int j=1;j<=x;j++){ 106 scanf("%d",&y); 107 update(dfn[y],dfn[y],c[y]); 108 a[j]=make_pair(dfn[y],dfn[y]+sz[y]-1); 109 } 110 sort(a+1,a+x+1); 111 st[0]=0; 112 for(int j=1;j<=x;j++){ 113 while ((st[0])&&(a[st[st[0]]].se<a[j].se))st[0]--; 114 v[idfn[a[st[st[0]]].fi]].push_back(idfn[a[j].fi]); 115 st[++st[0]]=j; 116 } 117 dfs(0); 118 } 119 if (p==2)printf("%lld ",query(x)); 120 } 121 } 122 return 0; 123 }