4034: [HAOI2015]树上操作

题目： 

 

---

 

 

题解：

　　 树剖裸题：

　　 麻烦一点的就只有子树修改（其实一点也不），因为子树编号连续啊，直接改段（记录编号最小和最大）

　　 开个long long 水模版

 　　 

---

 

 

代码：

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 using namespace std;  7 typedef long long LL;  8 struct node  9 { 10     int x,y,next; 11 }a[210000];int len,last[110000]; 12 void ins(int x,int y) 13 { 14     len++;a[len].x=x;a[len].y=y; 15     a[len].next=last[x];last[x]=len; 16 } 17 struct trnode 18 { 19     int l,r,lc,rc;LL c,lz; 20     trnode(){lz=0;} 21 }tr[210000];int trlen; 22 void update(int now) 23 { 24     if(tr[now].lz!=0) 25     { 26         int lc=tr[now].lc,rc=tr[now].rc; 27         if(lc!=-1)tr[lc].c+=LL(tr[lc].r-tr[lc].l+1)*tr[now].lz,tr[lc].lz+=tr[now].lz; 28         if(rc!=-1)tr[rc].c+=LL(tr[rc].r-tr[rc].l+1)*tr[now].lz,tr[rc].lz+=tr[now].lz; 29         tr[now].lz=0; 30     } 31 } 32 void bt(int l,int r) 33 { 34     int now=++trlen; 35     tr[now].l=l;tr[now].r=r;tr[now].c=0; 36     tr[now].lc=tr[now].rc=-1; 37     if(l
          
           tot[son[x]])son[x]=y; 75 tot[x]+=tot[y]; 76 } 77 } 78 } 79 int tp,id,ys[110000],top[110000],L[110000],R[110000]; 80 void pre_tree_edge(int x,int tp) 81 { 82 ys[x]=++id;top[x]=tp;L[x]=id; 83 if(son[x]!=0)pre_tree_edge(son[x],tp); 84 for(int k=last[x];k;k=a[k].next) 85 { 86 int y=a[k].y; 87 if(y!=son[x] && y!=fa[x])pre_tree_edge(y,y); 88 } 89 R[x]=id; 90 } 91 LL sol(int x,int y) 92 { 93 LL ans=0;int tx=top[x],ty=top[y]; 94 while(tx!=ty) 95 { 96 if(dep[tx]>dep[ty])swap(tx,ty),swap(x,y); 97 ans+=getsum(1,ys[ty],ys[y]); 98 y=fa[ty];ty=top[y]; 99 }100 if(x==y)return ans+getsum(1,ys[x],ys[x]);101 else102 {103 if(dep[x]>dep[y])swap(x,y);104 return ans+getsum(1,ys[x],ys[y]);105 }106 }107 LL d[100000];108 int main()109 {110 scanf("%d%d",&n,&m);len=0;memset(last,0,sizeof(last));111 for(int i=1;i<=n;i++)scanf("%lld",&d[i]);112 for(int i=1;i