树链剖分板子

  1 struct Tree
  2 {
  3     int n, a[maxn];
  4 
  5     struct Edge
  6     {
  7         int v, next;
  8     }edge[maxn<<1];
  9     
 10     int head[maxn], tot;
 11     
 12     void add(int u, int v)
 13     {
 14         edge[tot].v = v;
 15         edge[tot].next = head[u];
 16         head[u] = tot++;
 17     }
 18 
 19     int fa[maxn], deep[maxn], son[maxn], size[maxn];
 20     int top[maxn], id[maxn], rk[maxn];
 21     int cnt;
 22 
 23     void dfs1(int x, int pre, int d)
 24     {
 25         size[x] = 1, deep[x] = d, fa[x] = pre;
 26         for (int i = head[x]; i != -1; i = edge[i].next)
 27         {
 28             int v = edge[i].v;
 29             if (v == pre) continue;
 30             dfs1(v, x, d + 1);
 31             size[x] += size[v];
 32             if (size[v] > size[son[x]])    son[x] = v;
 33         }
 34     }
 35 
 36     void dfs2(int x, int tp)
 37     {
 38         top[x] = tp, id[x] = ++cnt, rk[cnt] = x;
 39         if (son[x])    dfs2(son[x], tp);
 40         for (int i = head[x]; i != -1; i = edge[i].next)
 41         {
 42             int v = edge[i].v;
 43             if (v == fa[x] || v == son[x]) continue;
 44             dfs2(v, v);
 45         }
 46     }
 47 
 48     int sum[maxn << 2], lazy[maxn << 2];
 49 
 50     void push_up(int rt)
 51     {
 52         sum[rt] = (sum[ls] + sum[rs]);
 53     }
 54 
 55     void push_down(int rt,int l,int r)
 56     {
 57         int mid = (l + r) >> 1;
 58         sum[ls] += lazy[rt] * (mid - l + 1);
 59         sum[rs] += lazy[rt] * (r - mid);
 60         lazy[ls] += lazy[rt];
 61         lazy[rs] += lazy[rt];
 62         lazy[rt] = 0;
 63     }
 64 
 65     void build(int rt, int l, int r)
 66     {
 67         if (l == r)
 68         {
 69             sum[rt] = a[rk[l]];
 70             return;
 71         }
 72         int mid = (l + r) >> 1;
 73         build(ls,l,mid);
 74         build(rs,mid+1,r);
 75         push_up(rt);
 76     }
 77 
 78     void update(int rt, int l, int r, int ql, int qr, int val)
 79     {
 80         if (ql <= l && qr >= r)
 81         {
 82             lazy[rt] += val;
 83             sum[rt] += val * (r - l + 1);
 84             return;
 85         }
 86         push_down(rt, l, r);
 87         int mid = (l + r) >> 1;
 88         if (ql <= mid)    update(ls, l, mid, ql, qr, val);
 89         if (qr > mid)    update(rs, mid + 1, r, ql, qr, val);
 90         push_up(rt);
 91     }
 92 
 93     int query(int rt, int l, int r, int ql, int qr)
 94     {
 95         if (ql <= l && qr >= r)
 96         {
 97             return sum[rt];
 98         }
 99         push_down(rt, l, r);
100         int mid = (l + r) >> 1;
101         int res = 0;
102         if (ql <= mid) res += query(ls, l, mid, ql, qr);
103         if (qr > mid)    res += query(rs, mid + 1, r, ql, qr);
104         return res;
105     }
106 
107     int getSum(int x, int y)
108     {
109         int res = 0;
110         while (top[x] != top[y])
111         {
112             if (deep[x] < deep[y])    swap(x, y);
113             res += query(1, 1, n, id[top[x]], id[x]);
114             x = fa[top[x]];
115         }
116         if (id[x] > id[y])    swap(x, y);
117         return res + query(1, 1, n, id[x], id[y]);
118     }
119 
120     void Update(int x, int y, int val)
121     {
122         while (top[x] != top[y])
123         {
124             if (deep[top[x]] < deep[top[y]])    swap(x, y);
125             update(1, 1, n, id[top[x]], id[x], val);
126             x = fa[top[x]];
127         }
128         if (id[x] > id[y])    swap(x, y);
129         update(1, 1, n, id[x], id[y], val);
130     }
131 
132     void init()
133     {
134         memset(head, -1, sizeof head);
135         tot = 0, cnt = 0;
136         memset(lazy, 0, sizeof lazy);
137         memset(sum, 0, sizeof sum);
138         memset(son, 0, sizeof son);
139     }
140 };
View Code