竟然1A了蛤蛤蛤蛤蛤

这题用人话说就是给你一个不会动的树，让你求带权重心。

先解决一个问题：如果要求动态修改点权，并且要求多次询问求某点\(x\)的\(\sum_{i = 1}^n d_i\cdot dist(i, x)\)，怎么做？

很显然对于一个点\(x\)，对它造成贡献的点，可能是在以\(x\)为根的点分子树里的，也可能在\(x\)之外。但是一个不在该点分子树内的点要对\(x\)产生贡献，必须要经过\(x\)在分治树上的祖先。

所以我们可以考虑对每个重心，记录下它这个点分子树中所有点对该重心的贡献、对点分树上的父亲的贡献以及该点分子树的点权和。每次求答案时\(x\)所在的分治子树的贡献很好考虑，那考虑一下其分治树上祖先对\(x\)的贡献就行了。

那带权重心怎么求呢？如果我们把树的根变成带权重心，那么我们会发现越远离根则答案越劣。所以我们如果只往使得答案更小的地方走，那么最后一定会走到带权重心上。

我们考虑把这个过程放点分树上。从整棵树的重心开始往下走，每次如果发现有一条出边指向的点答案更好，那就往这个子结构（不是指向的点而是那个联通块的重心，否则时间复杂度不对）里走。最后走不动了，走到的点就是带权重心了。

求LCA我用的是\(O(logn)\)的树剖而不是\(O(1)\)搞法，但是跑的贼快（可能和树剖常数小有关？）。

吐槽一点，原题提到了每个点的度数不超过20，但是网上几乎所有OJ上该题的题面都没提到这一点……

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <set>
#include <vector>
#include <queue>
#include <stack>
typedef long long ll;
const int maxn = 100005;
const int maxe = maxn << 1;
int first[maxn];
int next[maxe], to[maxe];
ll dist[maxe];
void add_edge(int u, int v, ll d) {
  static int cnt = 0;
  cnt ++;
  next[cnt] = first[u];
  first[u] = cnt;
  to[cnt] = v;
  dist[cnt] = d;
}
 
int n;
int size[maxn], hson[maxn], fa[maxn], dep[maxn];
ll dis[maxn];
void dfs_1(int x, int father = 0, int depth = 1, ll d = 0) {
  size[x] = 1;
  fa[x] = father;
  dep[x] = depth;
  dis[x] = d;
  int max_siz = 0;
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(v != father) {
      dfs_1(v, x, depth + 1, d + dist[i]);
      size[x] += size[v];
      if(size[v] > max_siz) {
        max_siz = size[v];
        hson[x] = v;
      }
    }
  }
}
int dfn[maxn], top[maxn], tid[maxn];
void dfs_2(int x, int father = 0, int a = 1) {
  static int dfn_clk = 0;
  dfn[x] = ++ dfn_clk;
  tid[dfn[x]] = x;
  top[x] = a;
  if(!hson[x]) {
    return;
  } else {
    dfs_2(hson[x], x, a);
  }
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(v != father && v != hson[x]) {
      dfs_2(v, x, v);
    }
  }
}
int lca(int x, int y) {
  while(top[x] != top[y]) {
    if(dep[top[x]] < dep[top[y]]) std::swap(x, y);
    x = fa[top[x]];
  }
  if(dep[x] > dep[y]) {
    return y;
  } else {
    return x;
  }
}
ll calc_dist(int x, int y) {
  int l = lca(x, y);
  return dis[x] + dis[y] - 2LL * dis[l];
}

bool vis[maxn];
int siz[maxn];
void gen_siz(int x, int f = 0) {
  siz[x] = 1;
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(!vis[v] && v != f) {
      gen_siz(v, x);
      siz[x] += siz[v];
    }
  }
}
int nrt, rt;
void gen_rt(int x, int f = 0) {
  bool flag = (siz[x] * 2 >= siz[nrt]);
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(!vis[v] && v != f) {
      flag = (flag && (siz[v] * 2 <= siz[nrt]));
      gen_rt(v, x);
    }
  }
  if(flag) rt = x;
}
ll w[maxn];
int crt, cfa[maxn];
ll pans[maxn], give[maxn], sumv[maxn];
int point2[maxe];
/*
void search_p(int x, std::stack<int> *V, int f = 0) {
  V -> push(x);
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(!vis[v] && v != f) {
      search_p(v, V, x);
    }
  }
}
*/
int divide(int x) {
  nrt = rt = x;
  gen_siz(x); gen_rt(x);
  x = rt; vis[x] = true;
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(!vis[v]) {
      int ch = divide(v);
      point2[i] = ch;
      cfa[ch] = x;
    }
  }
  return x;
}
void update(int x, ll delta) {
  int p = x;
  while(p) {
    pans[p] += delta * calc_dist(p, x);
    if(p != crt) give[p] += delta * calc_dist(x, cfa[p]);
    sumv[p] += delta;
    p = cfa[p];
  }
}
ll get_ans(int x) {
  ll ans = pans[x];
  int p = x;
  while(p != crt) {
    int f = cfa[p];
    ans += pans[f] - give[p];
    ans += calc_dist(x, f) * (sumv[f] - sumv[p]);
    p = cfa[p];
  }
  return ans;
}
ll get_best() {
  int p = crt;
  std::stack<int> S;
  ll now_ans;
  while(true) {
    S.push(p); vis[p] = true;
    bool fix = true;
    now_ans = get_ans(p);
    for(int i = first[p]; i; i = next[i]) {
      int v = to[i];
      if(vis[v]) continue;
      if(get_ans(v) < now_ans) {
        fix = false;
        p = point2[i];
        break;
      }
    }
    if(fix) break;
  }
  while(!S.empty()) {
    int u = S.top(); S.pop();
    vis[u] = false;
  }
  return now_ans;
}

int main() {
  int q; scanf("%d%d", &n, &q);
  for(int i = 0; i < n - 1; i ++) {
    int u, v; ll d; scanf("%d%d%lld", &u, &v, &d);
    add_edge(u, v, d); add_edge(v, u, d);
  }
  dfs_1(1); dfs_2(1);
  crt = divide(1); memset(vis, 0, sizeof(vis));
  while(q --) {
    int u, e; scanf("%d%d", &u, &e);
    update(u, e);
    printf("%lld\n", get_best());
  }
  return 0;
}

• 相关文章
• 全局相关文章