题解 P3676 【小清新数据结构题】

· · 题解

一共只有两个错误我竟然调了一个小时...（我才不会说我快读没判负数然后连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;
}