自动搬运

查看原文

来自洛谷，原作者为

	_rqy **

搬运于2025-08-24 21:51:30，当前版本为作者最后更新于2017-12-25 10:07:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

一共只有两个错误我竟然调了一个小时...（我才不会说我快读没判负数然后连WA四次）

呐，这题根本用不着动态点分治这种高大上的东西，点分治都用不到，只要树剖瞎搞一搞就可以了。

为了方便计算，我们维护每个点当前权值，那么修改点权就转化为了增加点权。

我们先考虑如果没有换根操作。

那么，修改某个点的权值只会影响它所有祖先的“子树点权和”。

先树剖把问题转化到序列上，问题就变成了区间加和维护区间平方和。我们只需要在线段树上维护区间和和区间平方和，那么如果有一个区间加标记$a$，区间和就变成了$\sum_i(s_i+a)=a\times len+\sum_is_i$，区间平方和变成了$\sum_i(s_i+a)^2=a^2\times len+2a\sum_is_i+\sum_is_i^2$，直接维护即可。

再来考虑换根。假设原来的根是$1$，现在的根是$u$，那么可以发现“子树点权和”改变的点只有从$1$到$u$的路径上的点。假设这条路径是$1=u_0-u_1-u_2-...-u_k=u$，对应每个点的子树点权和是（以$1$为根）$a_k$和（以$u$为根）$b_k$那么答案是$ans_u=ans_1-\sum_{i=0}^ka_i^2+\sum_{i=0}^kb_i^2$，其中$ans_1$是以$1$为根时的答案。

容易知道$a_{i+1}+b_i=a_0=b_k$（都等于所有点的点权总和），所以有

$$ans_u=ans_1-\sum_{i=0}^ka_i^2+\sum_{i=0}^kb_i^2=ans_1-a_0^2-\sum_{i=1}^ka_i^2+b_k^2+\sum_{i=0}^{k-1}(a_0-a_{i+1})^2 $$

化简得

$$ans_u=ans_1+(k-1)a_0^2-2a_0\sum_{i=1}^ka_i$$

于是我们只需要统计出这条路径上的点的个数和子树点权和的和即可。于是在树剖上跑就可以了。时间复杂度$O(nlog^2n)$（如果你非要写$O(nlogn)$的LCT也没人拦着）

代码：

#include <cctype>
#include <cstdio>
#include <cstring>
typedef long long LL;
const LL N = 200050;
LL n;

inline char readChar() {
  static char buf[10000000], *p = buf, *end = buf;
  if (p == end) end = buf + fread(p = buf, sizeof(char), 10000000, stdin);
  return *(p++);
}

inline int readInt() {
  int ans = 0, c, f = 1;
  while (!isdigit(c = readChar())) if (c == '-') f *= -1;
  do ans = ans * 10 + c - '0';
  while (isdigit(c = readChar()));
  return ans * f;
}

namespace TreeChain{
LL A[N];
LL s[N];
LL pre[N], nxt[N * 2], to[N * 2], cnt;
LL dep[N], node[N], pos[N], top[N], fa[N], siz[N], belong[N], cnt2, cnt3;

inline void addEdge(LL x, LL y) {
  nxt[cnt] = pre[x];
  to[pre[x] = cnt++] = y;
  nxt[cnt] = pre[y];
  to[pre[y] = cnt++] = x;
}

void dfs1(LL x) {
  dep[x] = dep[fa[x]] + 1;
  siz[x] = 1;
  s[x] = A[x];
  for (LL i = pre[x]; ~i; i = nxt[i])
    if (to[i] != fa[x]) {
      fa[to[i]] = x;
      dfs1(to[i]);
      siz[x] += siz[to[i]];
      s[x] += s[to[i]];
    }
}

void dfs2(LL x, bool n = false) {
  if (n) {
    ++cnt2;
    top[cnt2] = x;
  }
  node[pos[x] = cnt3++] = x;
  belong[x] = cnt2;
  if (siz[x] > 1) {
    LL l = 0;
    for (LL i = pre[x]; ~i; i = nxt[i])
      if (to[i] != fa[x] && siz[to[i]] > siz[l])
        l = to[i];
    dfs2(l);
    for (LL i = pre[x]; ~i; i = nxt[i])
      if (to[i] != fa[x] && to[i] != l)
        dfs2(to[i], true);
  }
}

inline void work() {
  memset(pre, -1, sizeof pre);
  for (LL i = 1; i < n; ++i)
    addEdge(readInt(), readInt());
  for (LL i = 1; i <= n; ++i)
    A[i] = readInt();
  dfs1(1);
  cnt3 = 1;
  dfs2(1, true);
}
};

namespace SegTree{
LL ss[N * 4], ss2[N * 4], addv[N * 4];
#define lch (o << 1)
#define rch (o << 1 | 1)

inline void maintain(LL o, LL l, LL r) {
  using TreeChain::s;
  using TreeChain::node;
  if (l == r) {
    ss[o] = addv[o] + s[node[l]];
    ss2[o] = ss[o] * ss[o];
  } else {
    ss[o] = ss[lch] + ss[rch] + addv[o] * (r - l + 1);
    ss2[o] = ss2[lch] + ss2[rch] +
      addv[o] * addv[o] * (r - l + 1) + 2 * addv[o] * (ss[lch] + ss[rch]);
  }
}

inline void pushdown(LL o, LL l, LL r) {
  using TreeChain::s;
  using TreeChain::node;
  if (l == r) s[node[l]] += addv[o];
  else {
    addv[lch] += addv[o];
    addv[rch] += addv[o];
  }
  addv[o] = 0;
}

void build(LL o, LL l, LL r) {
  if (l != r) {
    LL mid = (l + r) / 2;
    build(lch, l, mid);
    build(rch, mid + 1, r);
  }
  maintain(o, l, r);
}

void modify(LL o, LL l, LL r, LL L, LL R, LL add) {
  if (l > R || r < L) return;
  if (r <= R && l >= L)
    addv[o] += add;
  else {
    LL mid = (l + r) / 2;
    modify(lch, l, mid, L, R, add);
    modify(rch, mid + 1, r, L, R, add);
  }
  maintain(o, l, r);
}

void query(LL o, LL l, LL r, LL L, LL R, LL &ans2, LL &ans) {
  maintain(o, l, r);
  if (l > R || r < L) return;
  if (r <= R && l >= L) {
    ans2 += ss2[o];
    ans += ss[o];
  } else {
    LL mid = (l + r) / 2;
    pushdown(o, l, r);
    query(lch, l, mid, L, R, ans2, ans);
    query(rch, mid + 1, r, L, R, ans2, ans);
  }
}
};

using TreeChain::A;
LL sa = 0;
LL query(LL x) {
  using SegTree::query;
  using TreeChain::belong;
  using TreeChain::pos;
  LL ans = 0, ss = 0, tmp;
  query(1, 1, n, 1, n, ans, tmp);
  LL k = 0;
  while (belong[x] != belong[1]) {
    LL top = TreeChain::top[belong[x]];
    k += pos[x] - pos[top] + 1;
    query(1, 1, n, pos[top], pos[x], tmp, ss);
    x = TreeChain::fa[top];
  }
  k += pos[x] - pos[1];
  query(1, 1, n, pos[1] + 1, pos[x], tmp, ss);
  return ans + sa * (k * sa - 2 * ss);
}

void modify(LL x, LL y) {
  using SegTree::modify;
  using TreeChain::belong;
  using TreeChain::pos;
  y -= A[x];
  A[x] += y;
  sa += y;
  while (x) {
    LL top = TreeChain::top[belong[x]];
    modify(1, 1, n, pos[top], pos[x], y);
    x = TreeChain::fa[top];
  }
}

int main() {
  n = readInt();
  LL q = readInt();
  TreeChain::work();
  sa = TreeChain::s[1];
  SegTree::build(1, 1, n);
  while (q--) {
    if (readInt() == 1) {
      LL x = readInt();
      LL y = readInt();
      modify(x, y);
    } else {
      LL x = readInt();
      printf("%lld\n", query(x));
    }
  }
  return 0;
}