danihao123's Blog

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

第一个想到的思路……就事动态的维护虚树，然后虚树上所有边的长度乘二就事答案。然后我们考虑一点……虚树求的时候需要对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;
}

aji圆方树毁我青春，，，省选现场看出来是圆方树但写不出点双滚粗。

显然可以割的点是某两个点的某一条简单路径上的割点，然后两点间的简单路劲的并就是圆方树上的路径，割点在圆方树上就是非叶子的圆点。我们求所有两点路径的并，就需要虚树。

然后做完了……直接建圆方树，每次询问建虚树xjb统计即可。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
const int maxn = 100005;
const int maxm = 200005;
std::vector<int> G[maxn];
void cz1() {
  for(int i = 0; i < maxn; i ++) {
    G[i].clear();
  }
}
void add_edge1(int u, int v) {
  G[u].push_back(v); G[v].push_back(u);
}

using pii = std::pair<int, int>;
int dcnt, bcc_cnt; int pre[maxn]; bool iscut[maxn];
int bccno[maxn]; std::vector<int> bcc[maxm];
int dfs(int x, int fa = -1) {
  static std::stack<pii> S;
  pre[x] = ++ dcnt; int low = pre[x];
  int cld = 0;
  for(auto v : G[x]) {
    pii e = std::make_pair(x, v);
    if(!pre[v]) {
      S.push(e); cld ++;
      int lowv = dfs(v, x);
      low = std::min(low, lowv);
      if(lowv >= pre[x]) {
        iscut[x] = true; bcc_cnt ++;
        bcc[bcc_cnt].clear();
        while(true) {
          pii ee = S.top(); S.pop();
          int f = ee.first, g = ee.second;
          if(bccno[f] != bcc_cnt) {
            bccno[f] = bcc_cnt;
            bcc[bcc_cnt].push_back(f);
          }
          if(bccno[g] != bcc_cnt) {
            bccno[g] = bcc_cnt;
            bcc[bcc_cnt].push_back(g);
          }
          if(f == x && g == v) break;
        }
      }
    } else if(pre[v] < pre[x] && v != fa) {
      S.push(e);
      low = std::min(low, pre[v]);
    }
  }
  return low;
}
int n, m;
void calc_bcc() {
  std::fill(pre, pre + 1 + n, 0);
  std::fill(iscut, iscut + 1 + n, false);
  std::fill(bccno, bccno + 1 + m, 0);
  dcnt = bcc_cnt = 0;
  for(int i = 1; i <= n; i ++) {
    if(!pre[i]) dfs(i);
  }
}

std::vector<int> G2[maxn + maxm];
void cz2() {
  for(int i = 0; i < maxn + maxm; i ++) G2[i].clear();
}
void add_edge2(int u, int v) {
  G2[u].push_back(v); G2[v].push_back(u);
}

int anc[maxn + maxm][19], dep[maxn + maxm], d[maxn + maxm];
int dfn[maxn + maxm], siz[maxn + maxm];
int cnt2;
void dfs_tree(int x, int fa = -1, int depth = 0, int s = 0) {
#ifdef LOCAL
  printf("V (%d, %d, %d, %d)\n", x, fa, depth, s);
#endif
  cnt2 ++; dfn[x] = cnt2; siz[x] = 1;
  d[x] = s; anc[x][0] = fa; dep[x] = depth;
  for(auto v : G2[x]) {
    if(v != fa) {
      dfs_tree(v, x, depth + 1, s + ((v <= n) ? 1 : 0));
      siz[x] += siz[v];
    }
  }
}
void process_lca() {
  memset(anc, -1, sizeof(anc));
  cnt2 = 0;
  int s = bcc_cnt + n; dfs_tree(n + 1);
#ifdef LOCAL
  printf("s : %d\n", s);
#endif
  for(int j = 1; (1 << j) < s; j ++) {
    for(int i = 1; i <= s; i ++) {
      int a = anc[i][j - 1];
      if(a != -1) anc[i][j] = anc[a][j - 1];
    }
  }
}
int lca(int x, int y) {
  if(dep[x] < dep[y]) std::swap(x, y);
  for(int j = 18; j >= 0; j --) {
    int a = anc[x][j];
    if(a != -1 && dep[a] >= dep[y]) {
      x = a;
    }
  }
  if(x == y) return x;
  for(int j = 18; j >= 0; j --) {
    int a1 = anc[x][j], a2 = anc[y][j];
    if(a1 != -1 && a2 != -1 && a1 != a2) {
      x = a1; y = a2;
    }
  }
  return anc[x][0];
}

void process() {
  calc_bcc();
  cz2();
  for(int i = 1; i <= bcc_cnt; i ++) {
    int id = n + i;
    for(auto u : bcc[i]) {
      add_edge2(u, id);
    }
  }
  process_lca();
}
int get_delta(int x, int y) { // y is x's ancestor.
  return (d[anc[x][0]] - d[y]);
}
bool is_anc(int fa, int bef) {
  int l1 = dfn[fa], r1 = dfn[fa] + siz[fa] - 1;
  int l2 = dfn[bef], r2 = dfn[bef] + siz[bef] - 1;
  return (l1 <= l2 && r2 <= r1);
}
int query(int sz) {
  std::vector<int> V;
  for(int i = 1; i <= sz; i ++) {
    int x; scanf("%d", &x);
    V.push_back(x);
  }
  std::sort(V.begin(), V.end(), [&](const int &i, const int &j) {
    return dfn[i] < dfn[j];
  });
  std::set<int> ds; ds.insert(V[0]);
  for(int i = 1; i < sz; i ++) {
    ds.insert(V[i]);
    ds.insert(lca(V[i - 1], V[i]));
  }
  V.clear(); for(auto u : ds) V.push_back(u);
  std::sort(V.begin(), V.end(), [&](const int &i, const int &j) {
    return dfn[i] < dfn[j];
  });
  std::stack<int> S;
  int ans = 0;
  for(int i = 0; i < V.size(); i ++) {
    int u = V[i];
    while(!S.empty() && !is_anc(S.top(), u)) {
      S.pop();
    }
    if(!S.empty()) {
#ifdef LOCAL
      printf("ans (%d, %d) : %d\n", u, S.top(), get_delta(u, S.top()));
#endif
      ans += get_delta(u, S.top());
    }
    S.push(u);
  }
  for(auto u : ds) {
    if(u <= n) ans ++;
  }
  ans -= sz;
  return ans;
}

int main() {
  int T; scanf("%d", &T);
  while(T --) {
    scanf("%d%d", &n, &m); cz1();
    for(int i = 1; i <= m; i ++) {
      int u, v; scanf("%d%d", &u, &v);
      add_edge1(u, v);
    }
    process();
    int q; scanf("%d", &q);
    while(q --) {
      int sz; scanf("%d", &sz);
      printf("%d\n", query(sz));
#ifdef LOCAL
      fflush(stdout);
#endif
    }
  }
  return 0;
}