虛樹

0.前言

若干年前會(huì)過一次，然后就不會(huì)了。
現(xiàn)在又會(huì)了。

1.虛樹

存在這樣一類問題，多次詢問，每次給你 \(k\) 個(gè)特殊/關(guān)鍵點(diǎn)，要求有關(guān)這 \(k\) 個(gè)點(diǎn)的某種信息，并且題目保證了或隱含了 \(\sum k \le lim\)，那么可以考慮使用虛樹解決。

虛樹，即將這 \(k\) 個(gè)點(diǎn)提出，并按照原樹上的節(jié)點(diǎn)關(guān)系，建立一棵大小約為 \(2k\) 的樹，可以在這棵樹上求答案。

這里僅介紹二次排序 + LCA 的建樹方法。

將關(guān)鍵點(diǎn)按照 dfs 序排序；
將排序后相鄰兩點(diǎn)的 LCA 加入，再按 dfs 序排序并去重；
連 \((LCA(ve_{i - 1},ve_i),ve_i)\) 的邊。

對于 2：一般會(huì)將點(diǎn) \(1\) 也加入，便于求答案。
因?yàn)榘凑?dfs 序排序了，所以相鄰兩點(diǎn)之間一定不會(huì)出現(xiàn) dfs 序介于他們倆到 LCA 的路徑上的點(diǎn)，正確性得證。

建樹時(shí)間復(fù)雜度：\(\mathcal{O(\sum k \log n)}\)。

2.題目

2.1.P2495 [SDOI2011] 消耗戰(zhàn)

板子題。

我們將虛樹建出，接下來考慮樹形 DP。

\(f_u\) 表示點(diǎn) \(u\) 與其子樹內(nèi)所有關(guān)鍵點(diǎn)斷開所需最小代價(jià)。
對于虛樹上 \((u,v)\)：若 \(v\) 是關(guān)鍵點(diǎn)，那么這條邊必須斷；否則判斷是斷這條邊代價(jià)更小還是在 \(v\) 的子樹中斷若干邊代價(jià)更小。
顯然答案為 \(f_1\)。

#include <bits/stdc++.h>

#define int long long
#define ll long long
#define ull unsigned long long
#define db double
#define ld long double
#define rep(i,l,r) for (int i = (int)(l); i <= (int)(r); ++ i )
#define rep1(i,l,r) for (int i = (int)(l); i >= (int)(r); -- i )
#define il inline
#define fst first
#define snd second
#define ptc putchar
#define Yes ptc('Y'),ptc('e'),ptc('s'),puts("")
#define No ptc('N'),ptc('o'),puts("")
#define YES ptc('Y'),ptc('E'),ptc('S'),puts("")
#define NO ptc('N'),ptc('O'),puts("")
#define vi vector<int>
#define pb emplace_back
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define me(a,x) memset(a,x,sizeof a)
#define get(x) ((x - 1) / len + 1)
#define debug() puts("------------")

using namespace std;
typedef pair<int,int> PII;
typedef pair<int,PII> PIII;
typedef pair<ll,ll> PLL;
namespace szhqwq {
    template<class T> il void read(T &x) {
        x = 0; T f = 1; char ch = getchar();
        while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
        while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
        x *= f;
    }
    template<class T,class... Args> il void read(T &x,Args &...x_) { read(x); read(x_...); }
    template<class T> il void print(T x) {
        if (x < 0) ptc('-'), x = -x; 
        if (x > 9) print(x / 10); ptc(x % 10 + '0');
    }
    template<class T,class T_> il void write(T x,T_ ch) { print(x); ptc(ch); }
    template<class T,class T_> il void chmax(T &x,T_ y) { x = x < (T)y ? (T)y : x; }
    template<class T,class T_> il void chmin(T &x,T_ y) { x = x > (T)y ? (T)y : x; }
    template<class T,class T_,class T__> il T qmi(T a,T_ b,T__ p) {
        T res = 1; while (b) {
            if (b & 1) res = res * a % p;
            a = a * a % p; b >>= 1;
        } return res;
    }
    template<class T> il T gcd(T a,T b) { if (!b) return a; return gcd(b,a % b); }
    template<class T,class T_> il void exgcd(T a, T b, T_ &x, T_ &y) {
        if (b == 0) { x = 1; y = 0; return; }
        exgcd(b,a % b,y,x); y -= a / b * x; return ;
    }
    template<class T,class T_> il T getinv(T x,T_ p) { 
        T inv,y; exgcd(x,(T)p,inv,y);
        inv = (inv + p) % p; return inv;
    }
} using namespace szhqwq;
const int N = 5e5 + 10,inf = 1e9,mod = 998244353;
const ull base = 131,base_ = 233;
const ll inff = 1e18;
const db eps = 1e-6;
int n,m; vector<PII> G[N];
int h[N],e[N],ne[N],w[N],idx,dfn[N],tot;
int d[N],fa[N][20],dis[N][20],f[N];
bool st[N];

il void add(int a,int b,int c) {
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx ++;
    return ;
}

il void dfs(int u,int faa,int val) {
    dfn[u] = ++ tot;
    fa[u][0] = faa; dis[u][0] = val;
    d[u] = d[faa] + 1;
    rep(i,1,18) 
        fa[u][i] = fa[fa[u][i - 1]][i - 1],
        dis[u][i] = min(dis[u][i - 1],dis[fa[u][i - 1]][i - 1]);
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == faa) continue;
        dfs(j,u,w[i]);
    }
    return ;
}

il int LCA(int x,int y) {
    if (d[x] < d[y]) swap(x,y);
    rep1(i,18,0) if (d[fa[x][i]] >= d[y]) x = fa[x][i];
    if (x == y) return x;
    rep1(i,18,0) if (fa[x][i] != fa[y][i]) x = fa[x][i],y = fa[y][i];
    return fa[x][0];
}

il int calc(int x,int p) {
    int ret = inf;
    rep1(i,18,0) if (d[fa[x][i]] >= d[p])
        chmin(ret,dis[x][i]),x = fa[x][i];
    return ret;
}

il void dfss(int u,int faa) {
    f[u] = 0;
    for (auto x : G[u]) {
        int v = x.fst,w = x.snd;
        if (v == faa) continue;
        dfss(v,u);
        if (st[v]) f[u] += w;
        else f[u] += min(f[v],w);
    }
    return ;
}

il void solve() {
    //------------code------------
    me(h,-1); me(dis,0x3f);
    read(n);
    rep(i,1,n - 1) {
        int a,b,c; read(a,b,c);
        add(a,b,c); add(b,a,c);
    }
    dfs(1,0,inf);
    read(m);
    while (m -- ) {
        int k; read(k);
        vi v,ve;
        rep(i,1,k) {
            int x; read(x);
            v.pb(x);
        }
        sort(all(v),[](int x,int y){ return dfn[x] < dfn[y]; });
        ve.pb(1); ve.pb(v[0]);
        rep(i,1,k - 1) 
            ve.pb(LCA(v[i - 1],v[i])),
            ve.pb(v[i]);
        sort(all(ve),[](int x,int y){ return dfn[x] < dfn[y]; });
        ve.erase(unique(all(ve)),ve.end());
        rep(i,0,sz(ve) - 1) st[ve[i]] = 0,G[ve[i]].clear();
        for (auto x : v) st[x] = 1;
        rep(i,1,sz(ve) - 1) {
            int lca = LCA(ve[i - 1],ve[i]);
            G[lca].pb(ve[i],calc(ve[i],lca));
        }
        dfss(1,0); write(f[1],'\n');
    }
    return ;
}

il void init() {
    return ;
}

signed main() {
    // init();
    int _ = 1;
    // read(_);
    while (_ -- ) solve();
    return 0;
}

2.2.CF613D Kingdom and its Cities

同樣建出虛樹。要使所有關(guān)鍵點(diǎn)兩兩不連通，因?yàn)辄c(diǎn)權(quán)相同，可以直接貪心。

先判掉無解的情況。
若當(dāng)前點(diǎn) \(u\) 是關(guān)鍵點(diǎn)且其子樹中存在其他關(guān)鍵點(diǎn)，那么子樹中有多少關(guān)鍵點(diǎn)答案就加多少；
否則看子樹中有多少關(guān)鍵點(diǎn)，若有 \(> 1\) 個(gè)，那么占領(lǐng) \(u\) 點(diǎn)一定不劣；如果僅有 \(1\) 個(gè)，考慮放到父親節(jié)點(diǎn)及上面進(jìn)行處理一定更優(yōu)。

#include <bits/stdc++.h>

// #define int long long
#define ll long long
#define ull unsigned long long
#define db double
#define ld long double
#define rep(i,l,r) for (int i = (int)(l); i <= (int)(r); ++ i )
#define rep1(i,l,r) for (int i = (int)(l); i >= (int)(r); -- i )
#define il inline
#define fst first
#define snd second
#define ptc putchar
#define Yes ptc('Y'),ptc('e'),ptc('s'),puts("")
#define No ptc('N'),ptc('o'),puts("")
#define YES ptc('Y'),ptc('E'),ptc('S'),puts("")
#define NO ptc('N'),ptc('O'),puts("")
#define vi vector<int>
#define pb emplace_back
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define me(a,x) memset(a,x,sizeof a)
#define get(x) ((x - 1) / len + 1)
#define debug() puts("------------")

using namespace std;
typedef pair<int,int> PII;
typedef pair<int,PII> PIII;
typedef pair<ll,ll> PLL;
namespace szhqwq {
    template<class T> il void read(T &x) {
        x = 0; T f = 1; char ch = getchar();
        while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
        while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
        x *= f;
    }
    template<class T,class... Args> il void read(T &x,Args &...x_) { read(x); read(x_...); }
    template<class T> il void print(T x) {
        if (x < 0) ptc('-'), x = -x; 
        if (x > 9) print(x / 10); ptc(x % 10 + '0');
    }
    template<class T,class T_> il void write(T x,T_ ch) { print(x); ptc(ch); }
    template<class T,class T_> il void chmax(T &x,T_ y) { x = x < (T)y ? (T)y : x; }
    template<class T,class T_> il void chmin(T &x,T_ y) { x = x > (T)y ? (T)y : x; }
    template<class T,class T_,class T__> il T qmi(T a,T_ b,T__ p) {
        T res = 1; while (b) {
            if (b & 1) res = res * a % p;
            a = a * a % p; b >>= 1;
        } return res;
    }
    template<class T> il T gcd(T a,T b) { if (!b) return a; return gcd(b,a % b); }
    template<class T,class T_> il void exgcd(T a, T b, T_ &x, T_ &y) {
        if (b == 0) { x = 1; y = 0; return; }
        exgcd(b,a % b,y,x); y -= a / b * x; return ;
    }
    template<class T,class T_> il T getinv(T x,T_ p) { 
        T inv,y; exgcd(x,(T)p,inv,y);
        inv = (inv + p) % p; return inv;
    }
} using namespace szhqwq;
const int N = 2e5 + 10,inf = 1e9,mod = 998244353;
const ull base = 131,base_ = 233;
const ll inff = 1e18;
const db eps = 1e-6;
int n,q,id[N],cnt,fa[N][20];
int h[N],e[N],ne[N],idx,d[N];
bool vis[N];
vi G[N];

il void add(int a,int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
    return ;
}

il void dfs(int u,int f) {
    fa[u][0] = f;
    d[u] = d[f] + 1;
    rep(i,1,18) fa[u][i] = fa[fa[u][i - 1]][i - 1];
    id[u] = ++ cnt;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == f) continue;
        dfs(j,u);
    }
    return ;
}

il int LCA(int x,int y) {
    if (d[x] < d[y]) swap(x,y);
    rep1(i,18,0) if (d[fa[x][i]] >= d[y]) x = fa[x][i];
    if (x == y) return x;
    rep1(i,18,0) if (fa[x][i] != fa[y][i]) x = fa[x][i],y = fa[y][i];
    return fa[x][0];
}

int ret = 0,st[N];
il void calcans(int u) {
    if (vis[u]) st[u] = 1;
    int tot = 0;
    for (auto v : G[u]) {
        calcans(v);
        tot += st[v];
    }
    if (vis[u] && tot) ret += tot;
    else if (tot == 1) st[u] = 1;
    else if (tot > 1) ++ ret;
    return ;
}

il void solve() {
    //------------code------------
    read(n); me(h,-1);
    rep(i,1,n - 1) {
        int a,b; read(a,b);
        add(a,b); add(b,a);
    }
    dfs(1,0);
    read(q);
    while (q -- ) {
        int k; read(k);
        vi v,ve;
        rep(i,1,k) {
            int x; read(x);
            v.pb(x);
        }
        sort(all(v),[](int x,int y){ return id[x] < id[y]; });
        ve.pb(1); ve.pb(v[0]);
        rep(i,1,sz(v) - 1)
            ve.pb(LCA(v[i - 1],v[i])),
            ve.pb(v[i]);
        sort(all(ve),[](int x,int y){ return id[x] < id[y]; });
        ve.erase(unique(all(ve)),ve.end());
        for (auto x : ve) G[x].clear(),vis[x] = vis[fa[x][0]] = 0,st[x] = 0;
        for (auto x : v) vis[x] = 1;
        bool fl = 1;
        for (auto x : v) if (vis[fa[x][0]]) { fl = 0; break; }
        if (!fl) { puts("-1"); continue; }
        rep(i,1,sz(ve) - 1) G[LCA(ve[i - 1],ve[i])].pb(ve[i]);
        ret = 0;
        calcans(1);
        write(ret,'\n');
    }
    return ;
}

il void init() {
    return ;
}

signed main() {
    // init();
    int _ = 1;
    // read(_);
    while (_ -- ) solve();
    return 0;
}

2.3.P3233 [HNOI2014] 世界樹

建虛樹，考慮 up and down DP。

\(f_u = (dist,id)\)，分別表示最短距離及編號(hào)。

分別向上向下更新信息。

考慮最后計(jì)算答案怎么做。

對于虛樹上 \((u,v)\)，令 \(p\) 為 \(u\) 在原樹上和 \(v\) 那條鏈上的兒子。
如果兩點(diǎn)所屬的關(guān)鍵點(diǎn)相同，則 \(cnt_{id} \gets siz_p - siz_v\)。
若不同，則倍增跳到分界點(diǎn)，即上半部分所屬點(diǎn)與 \(u\) 相同，下半部分所屬點(diǎn)與 \(v\) 相同的點(diǎn) \(mid\)，\(mid\) 自己和 \(y\) 相同。
\(cnt_{id_u} \gets siz_p - siz_{mid},cnt_{id_v} \gets siz_{mid} - siz_v\)。

注意到 \(u\) 某些子樹中可能不存在關(guān)鍵點(diǎn)，那么這些子樹中的點(diǎn)顯然所屬與 \(u\) 一致，處理一下即可。

#include <bits/stdc++.h>

// #define int long long
#define ll long long
#define ull unsigned long long
#define db double
#define ld long double
#define rep(i,l,r) for (int i = (int)(l); i <= (int)(r); ++ i )
#define rep1(i,l,r) for (int i = (int)(l); i >= (int)(r); -- i )
#define il inline
#define fst first
#define snd second
#define ptc putchar
#define Yes ptc('Y'),ptc('e'),ptc('s'),puts("")
#define No ptc('N'),ptc('o'),puts("")
#define YES ptc('Y'),ptc('E'),ptc('S'),puts("")
#define NO ptc('N'),ptc('O'),puts("")
#define vi vector<int>
#define pb emplace_back
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define me(a,x) memset(a,x,sizeof a)
#define get(x) ((x - 1) / len + 1)
#define debug() puts("------------")

using namespace std;
typedef pair<int,int> PII;
typedef pair<int,PII> PIII;
typedef pair<ll,ll> PLL;
namespace szhqwq {
    template<class T> il void read(T &x) {
        x = 0; T f = 1; char ch = getchar();
        while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
        while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
        x *= f;
    }
    template<class T,class... Args> il void read(T &x,Args &...x_) { read(x); read(x_...); }
    template<class T> il void print(T x) {
        if (x < 0) ptc('-'), x = -x; 
        if (x > 9) print(x / 10); ptc(x % 10 + '0');
    }
    template<class T,class T_> il void write(T x,T_ ch) { print(x); ptc(ch); }
    template<class T,class T_> il void chmax(T &x,T_ y) { x = x < (T)y ? (T)y : x; }
    template<class T,class T_> il void chmin(T &x,T_ y) { x = x > (T)y ? (T)y : x; }
    template<class T,class T_,class T__> il T qmi(T a,T_ b,T__ p) {
        T res = 1; while (b) {
            if (b & 1) res = res * a % p;
            a = a * a % p; b >>= 1;
        } return res;
    }
    template<class T> il T gcd(T a,T b) { if (!b) return a; return gcd(b,a % b); }
    template<class T,class T_> il void exgcd(T a, T b, T_ &x, T_ &y) {
        if (b == 0) { x = 1; y = 0; return; }
        exgcd(b,a % b,y,x); y -= a / b * x; return ;
    }
    template<class T,class T_> il T getinv(T x,T_ p) { 
        T inv,y; exgcd(x,(T)p,inv,y);
        inv = (inv + p) % p; return inv;
    }
} using namespace szhqwq;
const int N = 3e5 + 10,inf = 1e9,mod = 998244353;
const ull base = 131,base_ = 233;
const ll inff = 1e18;
const db eps = 1e-6;
int n,q,d[N],fa[N][20],siz[N];
int h[N],e[N << 1],ne[N << 1],idx;
PII f[N]; int id[N],cnt;
vi G[N]; bool vis[N];
int ret[N];

il void add(int a,int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
    return ;
}

il void dfs(int u,int f) {
    d[u] = d[f] + 1;
    fa[u][0] = f; id[u] = ++ cnt;
    rep(i,1,18) fa[u][i] = fa[fa[u][i - 1]][i - 1];
    siz[u] = 1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == f) continue;
        dfs(j,u);
        siz[u] += siz[j];
    }
    return ;
}

il int LCA(int x,int y) {
    if (d[x] < d[y]) swap(x,y);
    rep1(i,18,0) if (d[fa[x][i]] >= d[y]) x = fa[x][i];
    if (x == y) return x;
    rep1(i,18,0) if (fa[x][i] != fa[y][i]) x = fa[x][i],y = fa[y][i];
    return fa[x][0];
}

il int getdis(int x,int y) {
    return d[x] + d[y] - 2 * d[LCA(x,y)];
}

il void dfs1(int u) {
    f[u] = {inf,0};
    if (vis[u]) f[u] = {0,u};
    for (auto v : G[u]) {
        dfs1(v);
        if (f[v].snd) {
            int val = getdis(u,f[v].snd);
            if (val < f[u].fst) f[u] = {val,f[v].snd};
            else if (val == f[u].fst) chmin(f[u].snd,f[v].snd);
        }
    }
    return ;
}

il void dfs2(int u) {
    for (auto v : G[u]) {
        if (f[u].snd) {
            int val = getdis(v,f[u].snd);
            if (val < f[v].fst) f[v] = {val,f[u].snd};
            else if (val == f[v].fst) chmin(f[v].snd,f[u].snd);
        }
        dfs2(v);
    }
    return ;
}

il void calcans(int u) {
    int val = siz[u];
    for (auto v : G[u]) {
        int p = v;
        rep1(i,18,0) if (d[fa[p][i]] > d[u]) p = fa[p][i];
        val -= siz[p];
        if (f[u].snd == f[v].snd) ret[f[u].snd] += siz[p] - siz[v];
        else {
            int mid = v;
            rep1(i,18,0) {
                int dis = getdis(f[u].snd,fa[mid][i]),diss = getdis(f[v].snd,fa[mid][i]);
                if (dis > diss || dis == diss && f[v].snd < f[u].snd) mid = fa[mid][i];
            }
            ret[f[u].snd] += siz[p] - siz[mid]; ret[f[v].snd] += siz[mid] - siz[v];
        }
        calcans(v);
    }
    ret[f[u].snd] += val;
    return ;
}

il void solve() {
    //------------code------------
    read(n); me(h,-1);
    rep(i,1,n - 1) {
        int a,b; read(a,b);
        add(a,b); add(b,a);
    }
    dfs(1,0);
    read(q);
    while (q -- ) {
        int m; read(m);
        vi v,ve,vec;
        rep(i,1,m) {
            int x; read(x);
            v.pb(x); vec.pb(x);
            ret[x] = 0;
        }
        sort(all(v),[](int x,int y){ return id[x] < id[y]; });
        ve.pb(1); ve.pb(v[0]);
        rep(i,1,sz(v) - 1)
            ve.pb(LCA(v[i - 1],v[i])),
            ve.pb(v[i]);
        sort(all(ve),[](int x,int y){ return id[x] < id[y]; });
        ve.erase(unique(all(ve)),ve.end());
        for (auto x : ve) G[x].clear(),vis[x] = 0;
        for (auto x : v) vis[x] = 1;
        rep(i,1,sz(ve) - 1) G[LCA(ve[i - 1],ve[i])].pb(ve[i]);
        dfs1(1); dfs2(1); calcans(1);
        for (auto x : vec) write(ret[x],' ');
        puts("");
    }
    return ;
}

il void init() {
    return ;
}

signed main() {
    // init();
    int _ = 1;
    // read(_);
    while (_ -- ) solve();
    return 0;
}

posted @ 2025-04-22 18:05 songszh 閱讀(38) 評(píng)論(0) 收藏舉報(bào)

刷新頁面返回頂部

szhqwq's blogs

aaa

虛樹