登录/ 注册
 找回密码
 立即注册
关闭

CSDN热搜

程序园 精品问答 技术交流 资源下载
返回列表 发新帖
首页 › 业界区 › 安全 ›虚树

虚树

鞠古香 2025-6-1 00:00:14
0.前言

若干年前会过一次，然后就不会了。
现在又会了。
1.虚树

存在这样一类问题，多次询问，每次给你 \(k\) 个特殊/关键点，要求有关这 \(k\) 个点的某种信息，并且题目保证了或隐含了 \(\sum k \le lim\)，那么可以考虑使用虚树解决。
虚树，即将这 \(k\) 个点提出，并按照原树上的节点关系，建立一棵大小约为 \(2k\) 的树，可以在这棵树上求答案。
这里仅介绍二次排序 + LCA 的建树方法。

  • 将关键点按照 dfs 序排序；
  • 将排序后相邻两点的 LCA 加入，再按 dfs 序排序并去重；
  • 连 \((LCA(ve_{i - 1},ve_i),ve_i)\) 的边。
对于 2：一般会将点 \(1\) 也加入，便于求答案。
因为按照 dfs 序排序了，所以相邻两点之间一定不会出现 dfs 序介于他们俩到 LCA 的路径上的点，正确性得证。
建树时间复杂度：\(\mathcal{O(\sum k \log n)}\)。
2.题目

2.1.P2495 [SDOI2011] 消耗战

板子题。
我们将虚树建出，接下来考虑树形 DP。
\(f_u\) 表示点 \(u\) 与其子树内所有关键点断开所需最小代价。
对于虚树上 \((u,v)\)：若 \(v\) 是关键点，那么这条边必须断；否则判断是断这条边代价更小还是在 \(v\) 的子树中断若干边代价更小。
显然答案为 \(f_1\)。
  1. #include <bits/stdc++.h>
  3. #define int long long
  4. #define ll long long
  5. #define ull unsigned long long
  6. #define db double
  7. #define ld long double
  8. #define rep(i,l,r) for (int i = (int)(l); i <= (int)(r); ++ i )
  9. #define rep1(i,l,r) for (int i = (int)(l); i >= (int)(r); -- i )
  10. #define il inline
  11. #define fst first
  12. #define snd second
  13. #define ptc putchar
  14. #define Yes ptc('Y'),ptc('e'),ptc('s'),puts("")
  15. #define No ptc('N'),ptc('o'),puts("")
  16. #define YES ptc('Y'),ptc('E'),ptc('S'),puts("")
  17. #define NO ptc('N'),ptc('O'),puts("")
  18. #define vi vector<int>
  19. #define pb emplace_back
  20. #define sz(x) (int)(x.size())
  21. #define all(x) x.begin(),x.end()
  22. #define me(a,x) memset(a,x,sizeof a)
  23. #define get(x) ((x - 1) / len + 1)
  24. #define debug() puts("------------")
  26. using namespace std;
  27. typedef pair<int,int> PII;
  28. typedef pair<int,PII> PIII;
  29. typedef pair<ll,ll> PLL;
  30. namespace szhqwq {
  31.     template<class T> il void read(T &x) {
  32.         x = 0; T f = 1; char ch = getchar();
  33.         while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
  34.         while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
  35.         x *= f;
  36.     }
  37.     template<class T,class... Args> il void read(T &x,Args &...x_) { read(x); read(x_...); }
  38.     template<class T> il void print(T x) {
  39.         if (x < 0) ptc('-'), x = -x;
  40.         if (x > 9) print(x / 10); ptc(x % 10 + '0');
  41.     }
  42.     template<class T,class T_> il void write(T x,T_ ch) { print(x); ptc(ch); }
  43.     template<class T,class T_> il void chmax(T &x,T_ y) { x = x < (T)y ? (T)y : x; }
  44.     template<class T,class T_> il void chmin(T &x,T_ y) { x = x > (T)y ? (T)y : x; }
  45.     template<class T,class T_,class T__> il T qmi(T a,T_ b,T__ p) {
  46.         T res = 1; while (b) {
  47.             if (b & 1) res = res * a % p;
  48.             a = a * a % p; b >>= 1;
  49.         } return res;
  50.     }
  51.     template<class T> il T gcd(T a,T b) { if (!b) return a; return gcd(b,a % b); }
  52.     template<class T,class T_> il void exgcd(T a, T b, T_ &x, T_ &y) {
  53.         if (b == 0) { x = 1; y = 0; return; }
  54.         exgcd(b,a % b,y,x); y -= a / b * x; return ;
  55.     }
  56.     template<class T,class T_> il T getinv(T x,T_ p) {
  57.         T inv,y; exgcd(x,(T)p,inv,y);
  58.         inv = (inv + p) % p; return inv;
  59.     }
  60. } using namespace szhqwq;
  61. const int N = 5e5 + 10,inf = 1e9,mod = 998244353;
  62. const ull base = 131,base_ = 233;
  63. const ll inff = 1e18;
  64. const db eps = 1e-6;
  65. int n,m; vector<PII> G[N];
  66. int h[N],e[N],ne[N],w[N],idx,dfn[N],tot;
  67. int d[N],fa[N][20],dis[N][20],f[N];
  68. bool st[N];
  70. il void add(int a,int b,int c) {
  71.     e[idx] = b;
  72.     w[idx] = c;
  73.     ne[idx] = h[a];
  74.     h[a] = idx ++;
  75.     return ;
  76. }
  78. il void dfs(int u,int faa,int val) {
  79.     dfn[u] = ++ tot;
  80.     fa[u][0] = faa; dis[u][0] = val;
  81.     d[u] = d[faa] + 1;
  82.     rep(i,1,18)
  83.         fa[u][i] = fa[fa[u][i - 1]][i - 1],
  84.         dis[u][i] = min(dis[u][i - 1],dis[fa[u][i - 1]][i - 1]);
  85.     for (int i = h[u]; ~i; i = ne[i]) {
  86.         int j = e[i];
  87.         if (j == faa) continue;
  88.         dfs(j,u,w[i]);
  89.     }
  90.     return ;
  91. }
  93. il int LCA(int x,int y) {
  94.     if (d[x] < d[y]) swap(x,y);
  95.     rep1(i,18,0) if (d[fa[x][i]] >= d[y]) x = fa[x][i];
  96.     if (x == y) return x;
  97.     rep1(i,18,0) if (fa[x][i] != fa[y][i]) x = fa[x][i],y = fa[y][i];
  98.     return fa[x][0];
  99. }
  101. il int calc(int x,int p) {
  102.     int ret = inf;
  103.     rep1(i,18,0) if (d[fa[x][i]] >= d[p])
  104.         chmin(ret,dis[x][i]),x = fa[x][i];
  105.     return ret;
  106. }
  108. il void dfss(int u,int faa) {
  109.     f[u] = 0;
  110.     for (auto x : G[u]) {
  111.         int v = x.fst,w = x.snd;
  112.         if (v == faa) continue;
  113.         dfss(v,u);
  114.         if (st[v]) f[u] += w;
  115.         else f[u] += min(f[v],w);
  116.     }
  117.     return ;
  118. }
  120. il void solve() {
  121.     //------------code------------
  122.     me(h,-1); me(dis,0x3f);
  123.     read(n);
  124.     rep(i,1,n - 1) {
  125.         int a,b,c; read(a,b,c);
  126.         add(a,b,c); add(b,a,c);
  127.     }
  128.     dfs(1,0,inf);
  129.     read(m);
  130.     while (m -- ) {
  131.         int k; read(k);
  132.         vi v,ve;
  133.         rep(i,1,k) {
  134.             int x; read(x);
  135.             v.pb(x);
  136.         }
  137.         sort(all(v),[](int x,int y){ return dfn[x] < dfn[y]; });
  138.         ve.pb(1); ve.pb(v[0]);
  139.         rep(i,1,k - 1)
  140.             ve.pb(LCA(v[i - 1],v[i])),
  141.             ve.pb(v[i]);
  142.         sort(all(ve),[](int x,int y){ return dfn[x] < dfn[y]; });
  143.         ve.erase(unique(all(ve)),ve.end());
  144.         rep(i,0,sz(ve) - 1) st[ve[i]] = 0,G[ve[i]].clear();
  145.         for (auto x : v) st[x] = 1;
  146.         rep(i,1,sz(ve) - 1) {
  147.             int lca = LCA(ve[i - 1],ve[i]);
  148.             G[lca].pb(ve[i],calc(ve[i],lca));
  149.         }
  150.         dfss(1,0); write(f[1],'\n');
  151.     }
  152.     return ;
  153. }
  155. il void init() {
  156.     return ;
  157. }
  159. signed main() {
  160.     // init();
  161.     int _ = 1;
  162.     // read(_);
  163.     while (_ -- ) solve();
  164.     return 0;
  165. }
复制代码
2.2.CF613D Kingdom and its Cities

同样建出虚树。要使所有关键点两两不连通，因为点权相同，可以直接贪心。
先判掉无解的情况。
若当前点 \(u\) 是关键点且其子树中存在其他关键点，那么子树中有多少关键点答案就加多少；
否则看子树中有多少关键点，若有 \(> 1\) 个，那么占领 \(u\) 点一定不劣；如果仅有 \(1\) 个，考虑放到父亲节点及上面进行处理一定更优。
  1. #include <bits/stdc++.h>
  3. // #define int long long
  4. #define ll long long
  5. #define ull unsigned long long
  6. #define db double
  7. #define ld long double
  8. #define rep(i,l,r) for (int i = (int)(l); i <= (int)(r); ++ i )
  9. #define rep1(i,l,r) for (int i = (int)(l); i >= (int)(r); -- i )
  10. #define il inline
  11. #define fst first
  12. #define snd second
  13. #define ptc putchar
  14. #define Yes ptc('Y'),ptc('e'),ptc('s'),puts("")
  15. #define No ptc('N'),ptc('o'),puts("")
  16. #define YES ptc('Y'),ptc('E'),ptc('S'),puts("")
  17. #define NO ptc('N'),ptc('O'),puts("")
  18. #define vi vector<int>
  19. #define pb emplace_back
  20. #define sz(x) (int)(x.size())
  21. #define all(x) x.begin(),x.end()
  22. #define me(a,x) memset(a,x,sizeof a)
  23. #define get(x) ((x - 1) / len + 1)
  24. #define debug() puts("------------")
  26. using namespace std;
  27. typedef pair<int,int> PII;
  28. typedef pair<int,PII> PIII;
  29. typedef pair<ll,ll> PLL;
  30. namespace szhqwq {
  31.     template<class T> il void read(T &x) {
  32.         x = 0; T f = 1; char ch = getchar();
  33.         while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
  34.         while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
  35.         x *= f;
  36.     }
  37.     template<class T,class... Args> il void read(T &x,Args &...x_) { read(x); read(x_...); }
  38.     template<class T> il void print(T x) {
  39.         if (x < 0) ptc('-'), x = -x;
  40.         if (x > 9) print(x / 10); ptc(x % 10 + '0');
  41.     }
  42.     template<class T,class T_> il void write(T x,T_ ch) { print(x); ptc(ch); }
  43.     template<class T,class T_> il void chmax(T &x,T_ y) { x = x < (T)y ? (T)y : x; }
  44.     template<class T,class T_> il void chmin(T &x,T_ y) { x = x > (T)y ? (T)y : x; }
  45.     template<class T,class T_,class T__> il T qmi(T a,T_ b,T__ p) {
  46.         T res = 1; while (b) {
  47.             if (b & 1) res = res * a % p;
  48.             a = a * a % p; b >>= 1;
  49.         } return res;
  50.     }
  51.     template<class T> il T gcd(T a,T b) { if (!b) return a; return gcd(b,a % b); }
  52.     template<class T,class T_> il void exgcd(T a, T b, T_ &x, T_ &y) {
  53.         if (b == 0) { x = 1; y = 0; return; }
  54.         exgcd(b,a % b,y,x); y -= a / b * x; return ;
  55.     }
  56.     template<class T,class T_> il T getinv(T x,T_ p) {
  57.         T inv,y; exgcd(x,(T)p,inv,y);
  58.         inv = (inv + p) % p; return inv;
  59.     }
  60. } using namespace szhqwq;
  61. const int N = 2e5 + 10,inf = 1e9,mod = 998244353;
  62. const ull base = 131,base_ = 233;
  63. const ll inff = 1e18;
  64. const db eps = 1e-6;
  65. int n,q,id[N],cnt,fa[N][20];
  66. int h[N],e[N],ne[N],idx,d[N];
  67. bool vis[N];
  68. vi G[N];
  70. il void add(int a,int b) {
  71.     e[idx] = b;
  72.     ne[idx] = h[a];
  73.     h[a] = idx ++;
  74.     return ;
  75. }
  77. il void dfs(int u,int f) {
  78.     fa[u][0] = f;
  79.     d[u] = d[f] + 1;
  80.     rep(i,1,18) fa[u][i] = fa[fa[u][i - 1]][i - 1];
  81.     id[u] = ++ cnt;
  82.     for (int i = h[u]; ~i; i = ne[i]) {
  83.         int j = e[i];
  84.         if (j == f) continue;
  85.         dfs(j,u);
  86.     }
  87.     return ;
  88. }
  90. il int LCA(int x,int y) {
  91.     if (d[x] < d[y]) swap(x,y);
  92.     rep1(i,18,0) if (d[fa[x][i]] >= d[y]) x = fa[x][i];
  93.     if (x == y) return x;
  94.     rep1(i,18,0) if (fa[x][i] != fa[y][i]) x = fa[x][i],y = fa[y][i];
  95.     return fa[x][0];
  96. }
  98. int ret = 0,st[N];
  99. il void calcans(int u) {
  100.     if (vis[u]) st[u] = 1;
  101.     int tot = 0;
  102.     for (auto v : G[u]) {
  103.         calcans(v);
  104.         tot += st[v];
  105.     }
  106.     if (vis[u] && tot) ret += tot;
  107.     else if (tot == 1) st[u] = 1;
  108.     else if (tot > 1) ++ ret;
  109.     return ;
  110. }
  112. il void solve() {
  113.     //------------code------------
  114.     read(n); me(h,-1);
  115.     rep(i,1,n - 1) {
  116.         int a,b; read(a,b);
  117.         add(a,b); add(b,a);
  118.     }
  119.     dfs(1,0);
  120.     read(q);
  121.     while (q -- ) {
  122.         int k; read(k);
  123.         vi v,ve;
  124.         rep(i,1,k) {
  125.             int x; read(x);
  126.             v.pb(x);
  127.         }
  128.         sort(all(v),[](int x,int y){ return id[x] < id[y]; });
  129.         ve.pb(1); ve.pb(v[0]);
  130.         rep(i,1,sz(v) - 1)
  131.             ve.pb(LCA(v[i - 1],v[i])),
  132.             ve.pb(v[i]);
  133.         sort(all(ve),[](int x,int y){ return id[x] < id[y]; });
  134.         ve.erase(unique(all(ve)),ve.end());
  135.         for (auto x : ve) G[x].clear(),vis[x] = vis[fa[x][0]] = 0,st[x] = 0;
  136.         for (auto x : v) vis[x] = 1;
  137.         bool fl = 1;
  138.         for (auto x : v) if (vis[fa[x][0]]) { fl = 0; break; }
  139.         if (!fl) { puts("-1"); continue; }
  140.         rep(i,1,sz(ve) - 1) G[LCA(ve[i - 1],ve[i])].pb(ve[i]);
  141.         ret = 0;
  142.         calcans(1);
  143.         write(ret,'\n');
  144.     }
  145.     return ;
  146. }
  148. il void init() {
  149.     return ;
  150. }
  152. signed main() {
  153.     // init();
  154.     int _ = 1;
  155.     // read(_);
  156.     while (_ -- ) solve();
  157.     return 0;
  158. }
复制代码
2.3.P3233 [HNOI2014] 世界树

建虚树，考虑 up and down DP。
\(f_u = (dist,id)\)，分别表示最短距离及编号。
分别向上向下更新信息。
考虑最后计算答案怎么做。
对于虚树上 \((u,v)\)，令 \(p\) 为 \(u\) 在原树上和 \(v\) 那条链上的儿子。
如果两点所属的关键点相同，则 \(cnt_{id} \gets siz_p - siz_v\)。
若不同，则倍增跳到分界点，即上半部分所属点与 \(u\) 相同，下半部分所属点与 \(v\) 相同的点 \(mid\)，\(mid\) 自己和 \(y\) 相同。
\(cnt_{id_u} \gets siz_p - siz_{mid},cnt_{id_v} \gets siz_{mid} - siz_v\)。
注意到 \(u\) 某些子树中可能不存在关键点，那么这些子树中的点显然所属与 \(u\) 一致，处理一下即可。
  1. #include <bits/stdc++.h>
  3. // #define int long long
  4. #define ll long long
  5. #define ull unsigned long long
  6. #define db double
  7. #define ld long double
  8. #define rep(i,l,r) for (int i = (int)(l); i <= (int)(r); ++ i )
  9. #define rep1(i,l,r) for (int i = (int)(l); i >= (int)(r); -- i )
  10. #define il inline
  11. #define fst first
  12. #define snd second
  13. #define ptc putchar
  14. #define Yes ptc('Y'),ptc('e'),ptc('s'),puts("")
  15. #define No ptc('N'),ptc('o'),puts("")
  16. #define YES ptc('Y'),ptc('E'),ptc('S'),puts("")
  17. #define NO ptc('N'),ptc('O'),puts("")
  18. #define vi vector<int>
  19. #define pb emplace_back
  20. #define sz(x) (int)(x.size())
  21. #define all(x) x.begin(),x.end()
  22. #define me(a,x) memset(a,x,sizeof a)
  23. #define get(x) ((x - 1) / len + 1)
  24. #define debug() puts("------------")
  26. using namespace std;
  27. typedef pair<int,int> PII;
  28. typedef pair<int,PII> PIII;
  29. typedef pair<ll,ll> PLL;
  30. namespace szhqwq {
  31.     template<class T> il void read(T &x) {
  32.         x = 0; T f = 1; char ch = getchar();
  33.         while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
  34.         while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
  35.         x *= f;
  36.     }
  37.     template<class T,class... Args> il void read(T &x,Args &...x_) { read(x); read(x_...); }
  38.     template<class T> il void print(T x) {
  39.         if (x < 0) ptc('-'), x = -x;
  40.         if (x > 9) print(x / 10); ptc(x % 10 + '0');
  41.     }
  42.     template<class T,class T_> il void write(T x,T_ ch) { print(x); ptc(ch); }
  43.     template<class T,class T_> il void chmax(T &x,T_ y) { x = x < (T)y ? (T)y : x; }
  44.     template<class T,class T_> il void chmin(T &x,T_ y) { x = x > (T)y ? (T)y : x; }
  45.     template<class T,class T_,class T__> il T qmi(T a,T_ b,T__ p) {
  46.         T res = 1; while (b) {
  47.             if (b & 1) res = res * a % p;
  48.             a = a * a % p; b >>= 1;
  49.         } return res;
  50.     }
  51.     template<class T> il T gcd(T a,T b) { if (!b) return a; return gcd(b,a % b); }
  52.     template<class T,class T_> il void exgcd(T a, T b, T_ &x, T_ &y) {
  53.         if (b == 0) { x = 1; y = 0; return; }
  54.         exgcd(b,a % b,y,x); y -= a / b * x; return ;
  55.     }
  56.     template<class T,class T_> il T getinv(T x,T_ p) {
  57.         T inv,y; exgcd(x,(T)p,inv,y);
  58.         inv = (inv + p) % p; return inv;
  59.     }
  60. } using namespace szhqwq;
  61. const int N = 3e5 + 10,inf = 1e9,mod = 998244353;
  62. const ull base = 131,base_ = 233;
  63. const ll inff = 1e18;
  64. const db eps = 1e-6;
  65. int n,q,d[N],fa[N][20],siz[N];
  66. int h[N],e[N << 1],ne[N << 1],idx;
  67. PII f[N]; int id[N],cnt;
  68. vi G[N]; bool vis[N];
  69. int ret[N];
  71. il void add(int a,int b) {
  72.     e[idx] = b;
  73.     ne[idx] = h[a];
  74.     h[a] = idx ++;
  75.     return ;
  76. }
  78. il void dfs(int u,int f) {
  79.     d[u] = d[f] + 1;
  80.     fa[u][0] = f; id[u] = ++ cnt;
  81.     rep(i,1,18) fa[u][i] = fa[fa[u][i - 1]][i - 1];
  82.     siz[u] = 1;
  83.     for (int i = h[u]; ~i; i = ne[i]) {
  84.         int j = e[i];
  85.         if (j == f) continue;
  86.         dfs(j,u);
  87.         siz[u] += siz[j];
  88.     }
  89.     return ;
  90. }
  92. il int LCA(int x,int y) {
  93.     if (d[x] < d[y]) swap(x,y);
  94.     rep1(i,18,0) if (d[fa[x][i]] >= d[y]) x = fa[x][i];
  95.     if (x == y) return x;
  96.     rep1(i,18,0) if (fa[x][i] != fa[y][i]) x = fa[x][i],y = fa[y][i];
  97.     return fa[x][0];
  98. }
  100. il int getdis(int x,int y) {
  101.     return d[x] + d[y] - 2 * d[LCA(x,y)];
  102. }
  104. il void dfs1(int u) {
  105.     f[u] = {inf,0};
  106.     if (vis[u]) f[u] = {0,u};
  107.     for (auto v : G[u]) {
  108.         dfs1(v);
  109.         if (f[v].snd) {
  110.             int val = getdis(u,f[v].snd);
  111.             if (val < f[u].fst) f[u] = {val,f[v].snd};
  112.             else if (val == f[u].fst) chmin(f[u].snd,f[v].snd);
  113.         }
  114.     }
  115.     return ;
  116. }
  118. il void dfs2(int u) {
  119.     for (auto v : G[u]) {
  120.         if (f[u].snd) {
  121.             int val = getdis(v,f[u].snd);
  122.             if (val < f[v].fst) f[v] = {val,f[u].snd};
  123.             else if (val == f[v].fst) chmin(f[v].snd,f[u].snd);
  124.         }
  125.         dfs2(v);
  126.     }
  127.     return ;
  128. }
  130. il void calcans(int u) {
  131.     int val = siz[u];
  132.     for (auto v : G[u]) {
  133.         int p = v;
  134.         rep1(i,18,0) if (d[fa[p][i]] > d[u]) p = fa[p][i];
  135.         val -= siz[p];
  136.         if (f[u].snd == f[v].snd) ret[f[u].snd] += siz[p] - siz[v];
  137.         else {
  138.             int mid = v;
  139.             rep1(i,18,0) {
  140.                 int dis = getdis(f[u].snd,fa[mid][i]),diss = getdis(f[v].snd,fa[mid][i]);
  141.                 if (dis > diss || dis == diss && f[v].snd < f[u].snd) mid = fa[mid][i];
  142.             }
  143.             ret[f[u].snd] += siz[p] - siz[mid]; ret[f[v].snd] += siz[mid] - siz[v];
  144.         }
  145.         calcans(v);
  146.     }
  147.     ret[f[u].snd] += val;
  148.     return ;
  149. }
  151. il void solve() {
  152.     //------------code------------
  153.     read(n); me(h,-1);
  154.     rep(i,1,n - 1) {
  155.         int a,b; read(a,b);
  156.         add(a,b); add(b,a);
  157.     }
  158.     dfs(1,0);
  159.     read(q);
  160.     while (q -- ) {
  161.         int m; read(m);
  162.         vi v,ve,vec;
  163.         rep(i,1,m) {
  164.             int x; read(x);
  165.             v.pb(x); vec.pb(x);
  166.             ret[x] = 0;
  167.         }
  168.         sort(all(v),[](int x,int y){ return id[x] < id[y]; });
  169.         ve.pb(1); ve.pb(v[0]);
  170.         rep(i,1,sz(v) - 1)
  171.             ve.pb(LCA(v[i - 1],v[i])),
  172.             ve.pb(v[i]);
  173.         sort(all(ve),[](int x,int y){ return id[x] < id[y]; });
  174.         ve.erase(unique(all(ve)),ve.end());
  175.         for (auto x : ve) G[x].clear(),vis[x] = 0;
  176.         for (auto x : v) vis[x] = 1;
  177.         rep(i,1,sz(ve) - 1) G[LCA(ve[i - 1],ve[i])].pb(ve[i]);
  178.         dfs1(1); dfs2(1); calcans(1);
  179.         for (auto x : vec) write(ret[x],' ');
  180.         puts("");
  181.     }
  182.     return ;
  183. }
  185. il void init() {
  186.     return ;
  187. }
  189. signed main() {
  190.     // init();
  191.     int _ = 1;
  192.     // read(_);
  193.     while (_ -- ) solve();
  194.     return 0;
  195. }
复制代码
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

使用道具 举报
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册
发帖
鞠古香
2025-6-1 00:00:14

0

粉丝关注

24

主题发布

板块介绍填写区域，请于后台编辑
微信扫一扫