很多人说事动态虚树……其实也不算是吧，虽然这个东西用力虚树的思路惹。

第一个想到的思路……就事动态的维护虚树，然后虚树上所有边的长度乘二就事答案。然后我们考虑一点……虚树求的时候需要对DFS序（严格来说事欧拉序）排序，所以我们大致可以认为，虚树上做欧拉回路的本质就事按照DFS序扫描，换言之就事DFS一遍，然后进入和回溯事都把边记录到答案里，这个值也就事虚树上按DFS序排序之后两两相邻点的距离的和（首尾也要额外算一遍）。

然后这样一来，我们发现虚树上的非关键点就可以删掉了。因为非关键点也就是所有两两在DFS序中相邻的关键点的LCA，然后那两个关键点的距离也就等于他们到这个非关键点的距离的和。因此我们不需要维护非关键点，问题就简单了许多……

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <utility>
#include <set>
const int maxn = 100005;
using ll = long long;
using pii = std::pair<int, ll>;
std::vector<pii> G[maxn];
void add_edge(int u, int v, ll w) {
  G[u].push_back(pii(v, w));
}
void ins_edge(int u, int v, ll w) {
  add_edge(u, v, w); add_edge(v, u, w);
}

int anc[maxn][17];
int dep[maxn], dfn[maxn]; ll dis[maxn];
int dcnt = 0;
void dfs(int x, int fa = -1) {
  anc[x][0] = fa; dfn[x] = ++ dcnt;
  for(auto &e : G[x]) {
    int v = e.first; ll w = e.second;
    if(v != fa) {
      dep[v] = dep[x] + 1;
      dis[v] = dis[x] + w;
      dfs(v, x);
    }
  }
}
int n;
void process() {
  memset(anc, -1, sizeof(anc)); dfs(1);
  for(int j = 1; (1 << j) < n; j ++) {
    for(int i = 1; i <= n; i ++) {
      int a = anc[i][j - 1];
      if(a != -1) {
        anc[i][j] = anc[a][j - 1];
      }
    }
  }
}
int lca(int u, int v) {
  if(dep[u] < dep[v]) std::swap(u, v);
  for(int j = 16; j >= 0; j --) {
    int a = anc[u][j];
    if(a != -1 && dep[a] >= dep[v]) {
      u = a;
    }
  }
  if(u == v) return u;
  for(int j = 16; j >= 0; j --) {
    int a1 = anc[u][j], a2 = anc[v][j];
    if(a1 != -1 && a2 != -1 && a1 != a2) {
      u = a1; v = a2;
    }
  }
  return anc[u][0];
}
ll calc_dist(int u, int v) {
  return dis[u] + dis[v] - 2LL * dis[lca(u, v)];
}

// template <typename T>
struct Comp {
  bool operator ()(const int &a, const int &b) const {
    return dfn[a] < dfn[b];
  }
};
ll now = 0LL; std::set<int, Comp> S;
bool sta[maxn];
void add(int p) {
  auto suc = S.upper_bound(p);
  if(suc != S.begin()) {
    auto pre = -- suc; ++ suc;
    now += calc_dist(*pre, p);
    if(suc != S.end()) {
      now -= calc_dist(*pre, *suc);
    }
  }
  if(suc != S.end()) {
    now += calc_dist(*suc, p);
  }
  S.insert(p);
}
void del(int p) {
  auto suc = S.upper_bound(p);
  if(suc != S.end()) {
    now -= calc_dist(*suc, p);
  }
  if((*S.begin()) != p) {
    -- suc; -- suc;
    int prev = *suc;
    now -= calc_dist(prev, p);
    ++ suc; ++ suc;
    if(suc != S.end()) {
      now += calc_dist(prev, *suc);
    }
  }
  S.erase(p);
}
ll query() {
  if(S.size() <= 1) return 0LL;
  ll ret = now;
  auto las = S.end(); -- las;
  ret += calc_dist(*S.begin(), *las);
  return ret;
}

int main() {
  int m; scanf("%d%d", &n, &m);
  for(int i = 1; i <= n - 1; i ++) {
    int u, v, w; scanf("%d%d%d", &u, &v, &w);
    ins_edge(u, v, w);
  }
  process();
  while(m --) {
    int x; scanf("%d", &x);
    if(sta[x]) {
      del(x);
    } else {
      add(x);
    }
    sta[x] = !sta[x];
    printf("%lld\n", query());
  }
  return 0;
}

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