AC230祭!!(树链剖分)(180921更新)

今天闲的搜了一下.cpp...

神奇的Windows告诉我有499个文件;

吓得我赶紧写了一道水题...就500啦

虽然不多但是开心(^_^)

(附上树链表示庆祝)

树链剖分求LCA

复杂度忘了但是是本菜鸡已知的唯一能过luoguP3379的 = =

首先普及一下链(重链)

重链就是每次都从下两个儿子中选择较大的一个接上...

往下子孙的个数多的叫大儿子(回溯...)

根是第一个起点，找完一条链就从剩下的中选择深度dep最小的继续

然鹅有什么用??

求解过程:

①输入x,y

②求出链顶(起点)

③判断是否相同

如果相同:

LCA就是深度较小的那个(不解释),break

如果不同:

选择深度较深的往上走一步(省时啊!!)

⑤继续判断

⑨结束

②③覆盖x,y值

代码贴上(read()快读可以用标输)

18.09.21 更新

很久以前的blog……感慨颇多啊

前两天在网上到处搜最后还是看了自己的博客重新学会的……

粘一下代码lo

luoguP3384

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<cmath>
  6 #define rep(i,a,n) for(int i = a;i <= n;i++)
  7 #define per(i,n,a) for(int i = n;i >= a;i--)
  8 #define ls t<<1
  9 #define rs t<<1|1
 10 using namespace std;
 11 typedef long long ll;
 12 int read() {
 13     int as = 0,fu = 1;
 14     char c = getchar();
 15     while(c < '0' || c > '9') {
 16         if(c == '-') fu = -1;
 17         c = getchar();
 18     }
 19     while(c >= '0' && c <= '9') {
 20         as = as * 10 + c - '0';
 21         c = getchar();
 22     }
 23     return as * fu;
 24 }
 25 
 26 const int N = 200005;
 27 //head
 28 
 29 int n,T,s,mod;
 30 int cnt,cur,head[N],nxt[N],mo[N];
 31 int w[N],a[N],p[N<<2],add[N<<2];
 32 int id[N],pa[N],mson[N],top[N],sz[N],dep[N];
 33 
 34 void addline(int x,int y) {
 35     mo[++cnt] = y;
 36     nxt[cnt] = head[x];
 37     head[x] = cnt;
 38     mo[++cnt] = x;
 39     nxt[cnt] = head[y];
 40     head[y] = cnt;
 41     return;
 42 }
 43 
 44 void dfs1(int x,int fa,int d) {
 45     dep[x] = d;
 46     pa[x] = fa;
 47     sz[x] = 1;
 48     int maxson = -1;
 49     for(int i = head[x]; i; i = nxt[i]) {
 50         int sn = mo[i];
 51         if(sn == fa) continue;
 52         dfs1(sn,x,d+1);
 53         sz[x] += sz[sn];
 54         if(sz[sn] > maxson) {
 55             mson[x] = sn;
 56             maxson = sz[sn];
 57         }
 58     }
 59 }
 60 void dfs2(int x,int topx) {
 61     id[x] = ++cur;
 62     a[cur] = w[x];
 63     top[x] = topx;
 64     if(mson[x] == 0) return;
 65     dfs2(mson[x],topx);
 66     for(int i = head[x]; i; i = nxt[i]) {
 67         int sn = mo[i];
 68         if(sn == mson[x] || sn == pa[x]) continue;
 69         dfs2(sn,sn);
 70     }
 71     return;
 72 }
 73 
 74 inline void pup(int t) {
 75     p[t] = (p[ls] + p[rs]) % mod;
 76 }
 77 inline void pdown(int l,int r,int t) {
 78     if(add[t] == 0) return;
 79     int m = l+r >> 1;
 80     int szl = m+1-l;
 81     int szr = r-m;
 82     p[ls] = (p[ls] + add[t] * szl) % mod;
 83     p[rs] = (p[rs] + add[t] * szr) % mod;
 84     add[ls] = (add[ls] + add[t]) % mod;
 85     add[rs] = (add[rs] + add[t]) % mod;
 86     add[t] = 0;
 87     return;
 88 }
 89 void build(int l,int r,int t) {
 90     if(l == r) {
 91         p[t] = a[l];
 92         return;
 93     }
 94     int m = l+r >>1;
 95     build(l,m,ls);
 96     build(m+1,r,rs);
 97     pup(t);
 98     return;
 99 }
100 void Segupdate(int L,int R,int c,int l,int r,int t) {
101     if(L <= l && r <= R) {
102         p[t] = (p[t] + c * (r - l + 1)) % mod;
103         add[t] = (add[t] + c) % mod;
104         return;
105     }
106     pdown(l,r,t);
107     int m = l+r >> 1;
108     if(L <= m) Segupdate(L,R,c,l,m,ls);
109     if(R >  m) Segupdate(L,R,c,m+1,r,rs);
110     pup(t);
111     return;
112 }
113 int Segquery(int L,int R,int l,int r,int t) {
114     if(L <= l && r <= R) return p[t];
115     pdown(l,r,t);
116     int m = l+r >> 1;
117     int ans = 0;
118     if(L <= m) ans = (ans + Segquery(L,R,l,m,ls)) % mod;
119     if(R >  m) ans = (ans + Segquery(L,R,m+1,r,rs)) % mod;
120     return ans;
121 }
122 
123 void Lineupdate(int x,int y,int z) {
124     while(top[x] != top[y]) {
125         if(dep[top[x]] < dep[top[y]]) swap(x,y);
126         Segupdate(id[top[x]],id[x],z,1,n,1);
127         x = pa[top[x]];
128     }
129     if(dep[x] < dep[y]) swap(x,y);
130     Segupdate(id[y],id[x],z,1,n,1);
131     return;
132 }
133 int Linequery(int x,int y) {
134     int ans = 0;
135     while(top[x] != top[y]) {
136         if(dep[top[x]] < dep[top[y]]) swap(x,y);
137         ans = (ans + Segquery(id[top[x]],id[x],1,n,1)) % mod;
138         x = pa[top[x]];
139     }
140     if(dep[x] < dep[y]) swap(x,y);
141     ans = (ans + Segquery(id[y],id[x],1,n,1)) % mod;
142     return ans;
143 }
144 
145 void Sonupdate(int x,int z) {
146     Segupdate(id[x],id[x] + sz[x] - 1,z,1,n,1);
147     return;
148 }
149 int Sonquery(int x) {
150     return Segquery(id[x],id[x] + sz[x] - 1,1,n,1);
151 }
152 int main() {
153     n = read(),T = read(),s = read(),mod = read();
154     rep(i,1,n) w[i] = read() % mod;
155     rep(i,2,n) addline(read(),read());
156     dfs1(s,0,0);
157     dfs2(s,s);
158     build(1,n,1);
159     while(T--) {
160         int op = read();
161         if(op == 1) {
162             int x = read();
163             int y = read();
164             int z = read() % mod;
165             Lineupdate(x,y,z);
166         }
167         if(op == 2) {
168             int x = read();
169             int y = read();
170             printf("%d
",Linequery(x,y));
171         }
172         if(op == 3) {
173             int x = read();
174             int z = read() % mod;
175             Sonupdate(x,z);
176 
177         }
178         if(op == 4) {
179             int x = read();
180             printf("%d
",Sonquery(x));
181         }
182     }
183     return 0;
184 }

有点小小的忧伤啊……

> 别忘了总有人在等着你