[hdu7076]ZYB's kingdom

不难发现，操作1可以看作如下操作：对于删去$a_{1},a_{2},...,a_{k}$后的每一个连通块（的点集）$V$，令$\forall x\in V,x$的收益加上$s$（其中$s=\sum_{x\in V}c_{x}$）

考虑建立类似于虚树的东西，即将每一个$a_{i}$连到第一个在$a_{i}$中的祖先，接下来遍历这棵新树（森林），对每一个节点枚举其在原树上的所有儿子，考虑该儿子的子树，分类讨论：

1.若这棵子树中没有$a_{i}$中的点，直接暴力修改（对dfs序维护线段树）

2.若这棵子树中有$a_{i}$中的点，找到还是其儿子的点（同时在其该子树中），将这些子树的dfs区间在整个区间中删掉，即将整个区间划分为若干段分别查询后求和并（分别）修改

关于如何建立前者的虚树，可以将所有节点子树对应的dfs区间排序后遍历一遍，或者也可以建立虚树之后再删除不在$a_{i}$中的点，时间复杂度均为$o(k\log 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\n",query(x));

120         }

121     }

122     return 0;

123 }

巴特西

[hdu7076]ZYB's kingdom

最新文章

热门文章