对于既要支持子树修改又要支持链查询，

需要树链剖分

然后求出DFS序，DFS的时候先DFS重儿子，

然后子树是1个区间，链是$O(\log n)$个区间

 

这道题对于查询若干条链的并：

由于K<=5，所以考虑容斥原理

转化为查询若干条链的交，

假设有5条链ABCDE要求交

可以先求AB的交T,再求TC的交…

 

考虑如何求两条树链的交：

本题中树链保证是父亲到儿子

设两条链为(a,b)(x,y)，b是a的父亲，y是x的父亲

保存的交是(a',b')

c=lca(a,x)

如果c比b高或者c比y高，那么交集为空

否则a'=c

如果y在b的下面，那么b'=y，否则b'=b

 

每次查询$O(2^k(k\log n+\log^2n))$

 

常数优化：

因为对$2^{31}$取模，所以直接用int自然溢出即可，可快一倍

 

#include
     
      #include
      
       #define N 200010#define K 17using namespace std;int n,i,q,x,y,k,op,ed,g[N],v[N<<1],nxt[N<<1],st[N],en[N],dfn,d[N],f[N][18],son[N],size[N],top[N],ques[6][2],ans;inline void read(int&a){  char c;bool f=0;a=0;  while(!((((c=getchar())>='0')&&(c<='9'))||(c=='-')));  if(c!='-')a=c-'0';else f=1;  while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';  if(f)a=-a;}inline void addedge(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}inline int lca(int x,int y){  if(x==1||y==1)return 1;  if(x==y)return x;  if(d[x]
       
        =d[y])x=f[x][i];  if(x==y)return x;  for(int i=K;~i;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];  return f[x][0];}void dfs1(int x,int pre){  size[x]=1;d[x]=d[pre]+1;  int heavy=0,sizemax=0,i;  for(f[x][0]=pre,i=1;i<=K;i++)f[x][i]=f[f[x][i-1]][i-1];  for(i=g[x];i;i=nxt[i])if(v[i]!=pre){    dfs1(v[i],x),size[x]+=size[v[i]];    if(size[v[i]]>sizemax)sizemax=size[v[i]],heavy=v[i];  }  if(heavy)son[x]=heavy;}void dfs2(int x,int pre,int t){  st[x]=++dfn;top[x]=t;  if(son[x])dfs2(son[x],x,t);  for(int i=g[x];i;i=nxt[i])if(v[i]!=pre&&v[i]!=son[x])dfs2(v[i],x,v[i]);  en[x]=dfn;}int tot,l[N<<1],r[N<<1],len[N<<1],val[N<<1],tag[N<<1];int build(int a,int b){  int x=++tot;  len[x]=b-a+1;  if(a==b)return x;  int mid=(a+b)>>1;  l[x]=build(a,mid);r[x]=build(mid+1,b);  return x;}inline void add1(int x,int p){if(!x)return;val[x]+=len[x]*p;tag[x]+=p;}inline void pb(int x){if(tag[x]!=0)add1(l[x],tag[x]),add1(r[x],tag[x]),tag[x]=0;}inline void up(int x){val[x]=val[l[x]]+val[r[x]];}void add(int x,int a,int b,int c,int d,int p){  if(c<=a&&b<=d){add1(x,p);return;}  int mid=(a+b)>>1;  pb(x);  if(c<=mid)add(l[x],a,mid,c,d,p);  if(d>mid)add(r[x],mid+1,b,c,d,p);  up(x);}int ask(int x,int a,int b,int c,int d){  if(c<=a&&b<=d)return val[x];  int mid=(a+b)>>1,t=0;  pb(x);  if(c<=mid)t+=ask(l[x],a,mid,c,d);  if(d>mid)t+=ask(r[x],mid+1,b,c,d);  up(x);  return t;}inline int query(int x,int y){  if(x<1)return 0;  int t=0;  while(top[x]!=top[y])t+=ask(1,1,n,st[top[x]],st[x]),x=f[top[x]][0];  return t+ask(1,1,n,st[y],st[x]);}inline void merge(int&a,int&b,int x,int y){  if(a==0)return;  if(a==-1){a=x,b=y;return;}  int c=lca(a,x);  if(d[c]
        
         
          >1)+1;      printf("%d\n",ans);    }else{      read(x),read(y);      add(1,1,n,st[x],en[x],y);    }  }  return 0;}