• 周二. 11 月 12th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

[hdu7076]ZYB's kingdom

admin

11 月 28, 2021

不难发现,操作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 }

View Code

发表回复