【树剖】CF916E Jamie and Tree

迷南。 2023-06-01 06:09 17阅读 0赞

好吧这其实应该不是树剖...

因为只要求子树就够了，dfs就好了

大概就是记录一个全局根root

多画几幅图会发现修改时x,y以root为根时的lca为以1为根时的lca(x,y),lca(root,x),lca(root,y)中深度最大的一个

然后就可以做了

然后分类讨论当前更改操作节点x（更新即LCA(x,y),询问则就是x）和root的关系：

（接下来有关操作都以1为根）

> 1.x=root: 即询问/修改整颗树的权值和
> 
> 2.root不在x的子树内：这样的话这里x的子树是没有被影响到的，直接修改就好了
> 
> 3.root在x的子树内：画图发现（不会证明）从root到x的路径上的最后一个节点（不包括root和x）的子树是不要修改的，其他都要修改，这里用一下容斥就好了

维护区间和用线段树，lca用倍增（因为后面倍增还可以用来求路径，方便）

大概就好了

1 #include<bits/stdc++.h>
      2 #define int long long
      3 #define writeln(x)  write(x),puts("")
      4 using namespace std;
      5 inline int read(){
      6     int ans=0,f=1;char chr=getchar();
      7     while(!isdigit(chr)){
        if(chr=='-') f=-1;chr=getchar();}
      8     while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
      9     return ans*f;
     10 }void write(int x){
     11     if(x<0) putchar('-'),x=-x;
     12     if(x>9) write(x/10);
     13     putchar(x%10+'0');
     14 }const int M = 1e5+5;
     15 int head[M],ver[M<<1],nxt[M<<1],tot,n,m,dfn[M],b[M],a[M],fa[M][22],sz[M],T,dep[M],s[M<<2],lz[M<<2],root,x,y,z,t,ans;
     16 inline void add(int x,int y){ver[++tot]=y,nxt[tot]=head[x],head[x]=tot;}
     17 void dfs(int x,int f){
     18     dfn[x]=++T,fa[x][0]=f,b[dfn[x]]=a[x],dep[x]=dep[f]+1,sz[x]=1;
     19     for(int i=1;(1<<i)<=dep[x];i++)fa[x][i]=fa[fa[x][i-1]][i-1];
     20     for(int i=head[x];i;i=nxt[i]){
     21         if(ver[i]==f) continue;
     22         dfs(ver[i],x);
     23         sz[x]+=sz[ver[i]];
     24     }
     25 }
     26 int LCA(int x,int y){
     27     if(dep[x]<dep[y]) swap(x,y);
     28     for(int i=20;i>=0;i--)if(dep[x]-(1<<i)>=dep[y]) x=fa[x][i];
     29     if(x==y) return x;
     30     for(int i=20;i>=0;i--)
     31         if(fa[x][i]!=fa[y][i])
     32             x=fa[x][i],y=fa[y][i];
     33     return fa[x][0];
     34 }
     35 #define ls (i<<1)
     36 #define rs (i<<1|1)
     37 #define mid (l+r>>1)
     38 inline void Push_Up(int i){s[i]=s[ls]+s[rs];}
     39 inline void Push_Down(int i,int l,int r){
     40     if(!lz[i]) return;
     41     s[ls]+=lz[i]*(mid-l+1);
     42     s[rs]+=lz[i]*(r-mid);
     43     lz[ls]+=lz[i],lz[rs]+=lz[i];
     44     lz[i]=0;
     45 }
     46 void Build(int i,int l,int r){
     47     if(l==r) return (void)(s[i]=b[l]);
     48     Build(ls,l,mid),Build(rs,mid+1,r);
     49     Push_Up(i);
     50 }
     51 void Update(int i,int l,int r,int ql,int qr,int x){
     52     if(ql<=l&&r<=qr)return (void)(s[i]+=(r-l+1)*x,lz[i]+=x);
     53     Push_Down(i,l,r);
     54     if(ql<=mid) Update(ls,l,mid,ql,qr,x);
     55     if(qr>mid)  Update(rs,mid+1,r,ql,qr,x);
     56     Push_Up(i);
     57 } 
     58 int Query(int i,int l,int r,int ql,int qr){
     59     if(ql<=l&&r<=qr) return s[i];
     60     int ans=0;Push_Down(i,l,r);
     61     if(ql<=mid) ans+=Query(ls,l,mid,ql,qr);
     62     if(qr>mid)  ans+=Query(rs,mid+1,r,ql,qr);
     63     return ans;
     64 }
     65 inline int Get_Point(int x,int y){
     66     int l1=LCA(x,y),l2=LCA(x,root),l3=LCA(y,root);
     67     if(dep[l1]<dep[l2]) swap(l1,l2);
     68     if(dep[l1]<dep[l3]) swap(l1,l3);
     69     return l1;
     70 }
     71 inline Get(int x,int d){
        for(int i=20;i>=0;i--) if((1<<i)&d) x=fa[x][i];return x;}
     72 inline void Solve_1(){
     73     x=read(),y=read(),z=read();
     74     t=Get_Point(x,y);
     75     if(t==root) return (void)(Update(1,1,n,1,n,z));
     76     if(dfn[t]>dfn[root]||dfn[t]+sz[t]-1<dfn[root]) return (void)(Update(1,1,n,dfn[t],dfn[t]+sz[t]-1,z));
     77     int tmp=Get(root,dep[root]-dep[t]-1);
     78     Update(1,1,n,1,n,z);Update(1,1,n,dfn[tmp],dfn[tmp]+sz[tmp]-1,-z);
     79 }
     80 inline void Solve_2(){
     81     x=read();
     82     if(x==root) return (void)(writeln(Query(1,1,n,1,n)));
     83     if(dfn[x]>dfn[root]||dfn[x]+sz[x]-1<dfn[root]) return (void)(writeln(Query(1,1,n,dfn[x],dfn[x]+sz[x]-1)));
     84     int tmp=Get(root,dep[root]-dep[x]-1);
     85     ans=Query(1,1,n,1,n);ans-=Query(1,1,n,dfn[tmp],dfn[tmp]+sz[tmp]-1);
     86     writeln(ans);
     87 }
     88 signed main(){
     89     n=read(),m=read();
     90     for(int i=1;i<=n;i++) a[i]=read();
     91     for(int i=1;i<n;i++)x=read(),y=read(),add(x,y),add(y,x);
     92     dfs(1,0);Build(1,1,n);root=1;
     93     while(m--){
     94         int opt=read();
     95         if(opt==1) root=read();
     96         if(opt==2) Solve_1();
     97         if(opt==3) Solve_2();
     98     }
     99     return 0;
    100 }

转载于:https://www.cnblogs.com/zhenglw/p/11289420.html