树pao(雾) -一个渣渣

今天难得睡醒了，大概睡了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 }

转载自原文链接, 如需删除请联系管理员。

原文链接：树pao(雾)，转载请注明来源！