今天难得睡醒了，大概睡了13个小时，打算今晚把树剖学了。

嘿嘿嘿雀魂真好玩，这篇文章咕了

有学上了，找到了水平远高于我的队友，好开心的说，，，

卡空间感觉治不了了。。。

板子题是洛谷P3384

实在不知道怎么优化了，感觉应该是哪里写错了，但是是MLE又不是WA，明天再说惹

参考博客：

https://www.cnblogs.com/pks-t/p/9194322.html#_label0

https://www.cnblogs.com/George1994/p/7821357.html

下面那篇要好懂一些，码风也不错。所以为什么还要粘上面的呢？

其实树剖真不难。。就是码量大一些，如果你会 线段树，dfs序，lca。那么应该一看就懂了。

树剖其实就是把一个树剖成很多条链，然后在链上搞来搞去。

先来了解一下概念 

• 重结点：子树结点数目最多的结点；
• 轻节点：父亲节点中除了重结点以外的结点；
• 重边：父亲结点和重结点连成的边；
• 轻边：父亲节点和轻节点连成的边；
• 重链：由多条重边连接而成的路径；
• 轻链：由多条轻边连接而成的路径；

讯享网

然后有几个结论，不会证真的不会证，·········  记不得了，可以看上面blog

反正就是告诉你我们这样搞不会t。。。

那么我们怎么维护呢

比方说我们要  求 x 到 y 的路径长。

当x与y不在一条重链上时，我们可以 往上跳，跳到 top[x]这个位置，然后累加这一段答案，因为x与top[x]在一条重链所以很简单。

这样跳呀跳呀就跳到一条重链上去了。 然后再算一下就阔以了。

为什么不会T呢？复杂度是什么呢？这些我都不会。

同理 更新操作也是一样的。

如果对子树呢? 显然子树内的序号都是连续的。所以直接对 tid[x],tid[x]+siz[x]-1   这段区间搞来搞去就行了。

484很简单qwq

嗯敲代码的时候可就爽死你了

哦还没有说怎么算top，hson这些东西，可以先dfs一下求siz和hson。再dfs一下求top。具体看代码。

然后粘一个适合我自己码风的板子。vector的改天再说。因为自己平时喜欢vector。。。

要板子的话可以去看上面blog，真的讲得很好，每一步的代码什么的。

 1 #include <bits/stdc++.h>  2 typedef long long ll;  3 using namespace std;  4 inline int read() {  5 int X=0,w=1; char c=getchar();  6 while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }  7 while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();  8 return X*w;  9 }  10 const int N = 1e5+1;  11 struct Edge{  12 int to,next;  13 }edge[N];int cnt=0;int head[N];  14 void addEdge(int u,int v){  15 edge[++cnt].to=v;  16 edge[cnt].next=head[u];  17 head[u]=cnt;  18 }  19 struct Node{  20 int lz,val;  21 }tree[N];  22 int siz[N],top[N],hson[N],dep[N],fa[N],tid[N],ran[N];  23 int n,m,r,p,val[N],tot=0;  24 void dfs1(int u,int par,int d){  25 dep[u]=d;  26 fa[u]=par;  27 siz[u]=1;  28 for(int i=head[u];i;i=edge[i].next){  29 int v = edge[i].to;  30 if(v!=fa[u]){  31 dfs1(v,u,d+1);  32 siz[u]+=siz[v];  33 if(hson[u]==-1||siz[v]>siz[hson[u]]){  34 hson[u]=v;  35  }  36  }  37  }  38 }  39 void dfs2(int u,int t){  40 top[u]=t;  41 tid[u]=++tot;  42 ran[tot]=u;  43 if(!hson[u])return;  44  dfs2(hson[u],t);  45 for(int i=head[u];i;i=edge[i].next){  46 int v = edge[i].to;  47 if(v!=hson[u]&&v!=fa[u]){  48  dfs2(v,v);  49  }  50  }  51 }  52 void push_up(int x){  53 tree[x].val=(0ll+tree[x<<1].val+tree[x<<1|1].val)%p;  54 }  55 void push_down(int x,int l,int r){  56 if(!tree[x].lz)return;  57 int mid=l+r>>1;  58 tree[x<<1].val=(0ll+tree[x<<1].val+(mid-l+1)*tree[x].lz)%p;  59 tree[x<<1|1].val=(0ll+tree[x<<1|1].val+(r-mid)*tree[x].lz)%p;  60 tree[x<<1].lz=(0ll+tree[x<<1].lz+tree[x].lz)%p;  61 tree[x<<1|1].lz=(0ll+tree[x<<1|1].lz+tree[x].lz)%p;  62 tree[x].lz=0;  63 }  64 void build(int k,int l,int r){  65 if(l==r){  66 tree[k].val=val[ran[l]]%p;  67 } else{  68 int mid=l+r>>1;  69 build(k<<1,l,mid);  70 build(k<<1|1,mid+1,r);  71  push_up(k);  72  }  73 }  74 int query(int l,int r,int ql,int qr,int rt){  75 int res = 0;  76 if(ql<=l&&qr>=r){  77 res=(0ll+res+tree[rt].val)%p;  78 return res;  79  }  80 int mid = (l+r)>>1;  81  push_down(rt,l,r);  82 if(ql<=mid) res=(0ll+res+query(l,mid,ql,qr,rt<<1))%p;  83 if(qr>mid) res=(0ll+res+query(mid+1,r,ql,qr,rt<<1|1))%p;  84 return res;  85 }  86 void upd(int l,int r,int ul,int ur,int rt,int k){  87 if(ul<=l&&ur>=r) {  88 tree[rt].val = (tree[rt].val + k * (r - l + 1))%p;  89 tree[rt].lz+=k;  90 return;  91  }  92 int mid=l+r>>1;  93  push_down(rt,l,r);  94 if(ul<=mid)upd(l,mid,ul,ur,rt<<1,k);  95 if(ur>mid)upd(mid+1,r,ul,ur,rt<<1|1,k);  96  push_up(rt);  97 }  98 int query_p(int u,int v){ 
 
   
 //x  99 int ans=0; 100 while (top[u]!=top[v]){ 101 if(dep[top[u]]<dep[top[v]])swap(u,v); 102 ans=(0ll+ans%p+query(1,n,tid[top[u]],tid[u],1))%p; 103 u=fa[top[u]]; 104  } 105 if(dep[u]>dep[v])swap(u,v); 106 ans=(0ll+ans+query(1,n,tid[u],tid[v],1))%p; 107 return ans; 108 } 109 void upd_p(int u,int v,int z){ 110 z%=p; 111 while (top[u]!=top[v]){ 112 if(dep[top[u]]<dep[top[v]])swap(u,v); 113 upd(1,n,tid[top[u]],tid[u],1,z); 114 u=fa[top[u]]; 115  } 116 if(dep[u]>dep[v])swap(u,v); 117 upd(1,n,tid[u],tid[v],1,z); 118 } 119 int main(){ 120 n=read();m=read();r=read();p=read(); 121 for(int i=1;i<=n;i++)val[i]=read(); 122 int op,x,y,z; 123 for(int i=1;i<n;i++){ 124 x=read();y=read(); 125  addEdge(x,y); 126  addEdge(y,x); 127  } 128 dfs1(r,0,1); 129  dfs2(r,r); 130 build(1,1,n); 131 /**while (m--){ 132  op=read(); 133  if(op==1){ 134  x=read();y=read();z=read(); 135  upd_p(x,y,z); 136  } else if(op==2){ 137  x=read();y=read(); 138  printf("%d\n",query_p(x,y)); 139  } else if(op==3){ 140  x=read();z=read(); 141  upd(1,n,tid[x],tid[x]+siz[x]-1,1,z); 142  } else{ 143  x=read(); 144  printf("%d\n",query(1,n,tid[x],tid[x]+siz[x]-1,1)); 145  } 146  }*/ 147 }