[luoguP3178] [HAOI2015]树上操作（dfs序 + 线段树 || 树链剖分）

树链剖分固然可以搞。

但还有另一种做法，可以看出，增加一个节点的权值会对以它为根的整棵子树都有影响，相当于给整棵子树增加一个值。

而给以某一节点 x 为根的子树增加一个权值也会影响当前子树，节点 y 所增加的值为 dis[y] * z - (dis[x] - 1) * z，每个节点都会增加 -(dis[x] - 1) * z ，

询问时只用加上 dis[y] * y 和当前节点 y 的权值。

给整棵子树增加一个权值可以用 dfs 序 + 线段树搞， dis 数组可以预处理出来。

——代码

 #include <cstdio>

 #include <cstring>

 #define LL long long

 #define root 1, 1, n

 #define ls now << 1, l, mid

 #define rs now << 1 | 1, mid + 1, r

 using namespace std;

 const int MAXN = ;

 int n, m, cnt, tot;

 int head[MAXN], next[MAXN << ], to[MAXN << ], tid[MAXN], size[MAXN];

 LL a[MAXN << ], b[MAXN << ], val[MAXN], dis[MAXN];

 inline void add(int x, int y)

 {

     to[cnt] = y;

     next[cnt] = head[x];

     head[x] = cnt++;

 } 

 inline void dfs(int u)

 {

     int i, v;

     tid[u] = ++tot;

     size[u] = ;

     for(i = head[u]; i != -; i = next[i])

     {

         v = to[i];

         if(!size[v])

         {

             dis[v] = dis[u] + ;

             dfs(v);

             size[u] += size[v];

         }

     }

 }

 inline void push_down(int now)

 {

     a[now << ] += a[now];

     a[now <<  | ] += a[now];

     b[now << ] += b[now];

     b[now <<  | ] += b[now];

     a[now] = b[now] = ;

 }

 inline void update(LL x, LL y, int ql, int qr, int now, int l, int r)

 {

     if(ql <= l && r <= qr)

     {

         a[now] += x;

         b[now] += y;

         return;

     }

     push_down(now);

     int mid = (l + r) >> ;

     if(ql <= mid) update(x, y, ql, qr, ls);

     if(mid < qr) update(x, y, ql, qr, rs);

 }

 inline LL query(int u, int x, int now, int l, int r)

 {

     if(l == r) return dis[u] * a[now] + b[now];

     push_down(now);

     int mid = (l + r) >> ;

     if(x <= mid) return query(u, x, ls);

     else return query(u, x, rs);

 }

 int main()

 {

     int i, x, z;

     LL y;

     scanf("%d %d", &n, &m);

     for(i = ; i <= n; i++)    scanf("%lld", &val[i]);

     memset(head, -, sizeof(head));

     for(i = ; i < n; i++)

     {

         scanf("%d %d", &x, &y);

         add(x, y);

         add(y, x);

     }

     dis[] = ;

     dfs();

     for(i = ; i <= n; i++) update(, val[i], tid[i], tid[i] + size[i] - , root);

     for(i = ; i <= m; i++)

     {

         scanf("%d %d", &z, &x);

         if(z == )

         {

             scanf("%lld", &y);

             update(, y, tid[x], tid[x] + size[x] - , root);

         }

         else if(z == )

         {

             scanf("%lld", &y);

             update(y, -((dis[x] - ) * y), tid[x], tid[x] + size[x] - , root);

         }

         else printf("%lld\n", query(x, tid[x], root));

     }

     return ;

 }

巴特西

[luoguP3178] [HAOI2015]树上操作（dfs序 + 线段树 || 树链剖分）

最新文章

热门文章