学习笔记--虚树

基本上就是把一棵很大的树压缩一波成一棵比较小的树，然后对原树的询问就可以在这棵压缩信息的树上搞，以降低复杂度。

构建方法：见大佬博客https://www.cnblogs.com/zzqsblog/p/5560645.html

https://www.cnblogs.com/chenhuan001/p/5639482.html

大致思路：先按dfs序将所有结点排序，然后用栈维护到之前一个点为结尾的dfs链，分情况讨论，因为新来的点dfs序一定大于栈顶的，所以要么它和栈顶的lca是栈顶本身，要么则分立两边，那么如果是第一种就继续接下去，第二种则一直将栈弹至栈顶深度小于等于lca，再接上。

例题：洛谷2495 [SDOI2011]消耗战

链接：https://www.luogu.org/problemnew/show/P2495

代码：

// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define sc second
#define pii pair<int,int>
using namespace std;
const int N=300010;
void read(int &x)
{
    char c=getchar();x=0;
    while(!isdigit(c))c=getchar();
    while(isdigit(c))x=(x<<3)+(x<<1)+c-48,c=getchar();
}
vector<pii>mp[N];
int n,jp[N][20],mn[N][20],dfn[N],dep[N],tim=0;
void dfs(int pos,int fa,int tf)
{
    dfn[pos]=++tim,dep[pos]=dep[fa]+1;
    jp[pos][0]=fa,mn[pos][0]=tf;
    for(int i=1;i<=19;i++)
        jp[pos][i]=jp[jp[pos][i-1]][i-1],mn[pos][i]=min(mn[pos][i-1],mn[jp[pos][i-1]][i-1]);
    for(int i=0;i<mp[pos].size();i++)
        if(mp[pos][i].fi!=fa)dfs(mp[pos][i].fi,pos,mp[pos][i].sc);  
}
int lca(int x,int y)
{
    if(dep[x]<dep[y])swap(x,y);
    for(int i=19;i>=0;i--)
        if(dep[jp[x][i]]>=dep[y])x=jp[x][i];
    if(x==y)return x;
    for(int i=19;i>=0;i--)
        if(jp[x][i]!=jp[y][i])x=jp[x][i],y=jp[y][i];
    return jp[x][0];
}
int dis(int x,int fx)
{
    int res=2e9;
    for(int i=19;i>=0;i--)
        if(dep[jp[x][i]]>=dep[fx])
            res=min(res,mn[x][i]),x=jp[x][i];
    return res;
}
namespace Fake_tree{
    int k,imp[N],S[N],D[N],hd,fa[N];bool lab[N];
    vector<int>bin;ll ans[N];
    bool cmp(int x,int y)
    {return dfn[x]<dfn[y];}
    void build()
    {
        int tt=k,nw,f;
        sort(imp+1,imp+k+1,cmp);hd=0;
        for(int i=1;i<=k;i++)
        {
            nw=imp[i];
            if(!hd){fa[nw]=0,S[++hd]=nw;continue;}
            f=lca(nw,S[hd]);
            while(dep[S[hd]]>dep[f])
            {
                if(dep[S[hd-1]]<dep[f])fa[S[hd]]=f;
                --hd;
            }
            if(f!=S[hd])
            {
                imp[++tt]=f;
                fa[f]=S[hd];
                S[++hd]=f;
            }
            fa[nw]=f,S[++hd]=nw;
        }
        k=tt;sort(imp+1,imp+k+1,cmp);
    }
    void dfs()
    {
        int nw;
        for(int i=1;i<=k;i++)ans[imp[i]]=0;
        for(int i=k;i>=2;i--)nw=imp[i],ans[fa[nw]]+=(lab[nw]?D[nw]:min((ll)D[nw],ans[nw]));
    }
    void main()
    {
        read(k);
        for(int i=0;i<bin.size();i++)lab[bin[i]]=0;
        bin.clear();imp[1]=1,lab[1]=1,++k;
        for(int i=2;i<=k;i++)
            read(imp[i]),lab[imp[i]]=1,bin.push_back(imp[i]);
        build();
        for(int i=2;i<=k;i++)D[imp[i]]=dis(imp[i],fa[imp[i]]);dfs();
        printf("%lld\n",ans[1]);
    }
}
int main()
{
    int m,u,v,w;
    read(n);
    for(int i=1;i<n;i++)
    {
        read(u),read(v),read(w);
        mp[u].push_back(pii(v,w)),
        mp[v].push_back(pii(u,w));
    }
    dfs(1,0,0);
    read(m);
    for(int i=1;i<=m;i++)
        Fake_tree::main();
}