例①:P2495 [SDOI2011]消耗战:
题目描述
在一场战争中,战场由n个岛屿和n-1个桥梁组成,保证每两个岛屿间有且仅有一条路径可达。现在,我军已经侦查到敌军的总部在编号为1的岛屿,而且他们已经没有足够多的能源维系战斗,我军胜利在望。已知在其他k个岛屿上有丰富能源,为了防止敌军获取能源,我军的任务是炸毁一些桥梁,使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同,所以炸毁不同的桥梁有不同的代价,我军希望在满足目标的同时使得总代价最小。

侦查部门还发现,敌军有一台神秘机器。即使我军切断所有能源之后,他们也可以用那台机器。机器产生的效果不仅仅会修复所有我军炸毁的桥梁,而且会重新随机资源分布(但可以保证的是,资源不会分布到1号岛屿上)。不过侦查部门还发现了这台机器只能够使用m次,所以我们只需要把每次任务完成即可。

输入格式
第一行一个整数n,代表岛屿数量。

接下来n-1行,每行三个整数u,v,w,代表u号岛屿和v号岛屿由一条代价为c的桥梁直接相连,保证1<=u,v<=n且1<=c<=100000。

第n+1行,一个整数m,代表敌方机器能使用的次数。

接下来m行,每行一个整数ki,代表第i次后,有ki个岛屿资源丰富,接下来k个整数h1,h2,…hk,表示资源丰富岛屿的编号。

输出格式
输出有m行,分别代表每次任务的最小代价。

输入输出样例
输入 #1 复制
10
1 5 13
1 9 6
2 1 19
2 4 8
2 3 91
5 6 8
7 5 4
7 8 31
10 7 9
3
2 10 6
4 5 7 8 3
3 9 4 6
输出 #1 复制
12
32
22
说明/提示
【数据规模和约定】

对于10%的数据,2<=n<=10,1<=m<=5,1<=ki<=n-1

对于20%的数据,2<=n<=100,1<=m<=100,1<=ki<=min(10,n-1)

对于40%的数据,2<=n<=1000,m>=1,sigma(ki)<=500000,1<=ki<=min(15,n-1)

对于100%的数据,2<=n<=250000,m>=1,sigma(ki)<=500000,1<=ki<=n-1

题目分析:很明显这是一道虚树的题目,我们可以在dfs过程中求出dfn(x),minn(x)。
这道题目比较特殊,如果某棵子树的根节点需要断开,那么这棵子树中的其他节点不必再考虑。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<deque>
#include<map>
#include<vector>
#include<cmath>
#define ll long long
#define llu unsigned ll
using namespace std;
const double eps = 1e-8;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int maxn=500010;
const int mod=1e9+7;
const int maxm=250050;
int hh[maxm],vv[maxn],ee[maxn],nn[maxn];
int head[maxm],ver[maxm],nt[maxm];
int d[maxm],f[maxm][20],s[maxm],dfn[maxm],a[maxm];
ll minn[maxm],dp[maxm];
int t,tt=1,tot=1,cnt=0,top=0;

void add(int x,int y,int z)
{
    vv[++tt]=y,ee[tt]=z;
    nn[tt]=hh[x],hh[x]=tt;
}

void add(int x,int y)
{
    ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}

bool cmp(const int &a,const int &b)
{
    return dfn[a]<dfn[b];
}


void dfs(int x,int fa)
{
    dfn[x]=++cnt;
    for(int i=hh[x];i;i=nn[i])
    {
        int y=vv[i],z=ee[i];
        if(y==fa) continue;
        d[y]=d[x]+1;
        f[y][0]=x;
        minn[y]=min(minn[x],(ll)z);
        for(int j=1;j<=t;j++)
            f[y][j]=f[f[y][j-1]][j-1];
        dfs(y,x);
    }
}

int LCA(int x,int y)
{
    if(d[x]>d[y]) swap(x,y);
    for(int i=t;i>=0;i--)
        if(d[f[y][i]]>=d[x]) y=f[y][i];
    if(y==x) return x;
    for(int i=t;i>=0;i--)
        if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}

void in(int x)
{
    if(top==1)
    {
        s[++top]=x;
        return ;
    }
    int lca=LCA(s[top],x);
    if(lca==s[top]) return ;
    while(top>1&&dfn[s[top-1]]>=dfn[lca])
    {
        add(s[top-1],s[top]);
        top--;
    }
    if(lca!=s[top]) add(lca,s[top]),s[top]=lca;
    s[++top]=x;
}

void build(int k)
{
    for(int i=1;i<=k;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+k+1,cmp);

    s[top=1]=1;
    tot=1;
    for(int i=1;i<=k;i++)
        in(a[i]);
    while(top) add(s[top-1],s[top]),top--;
}

void DP(int x)
{
    //叶节点一定是需要断开的
    if(!head[x])
    {
        dp[x]=minn[x];
        return ;
    }
    dp[x]=0;
    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        DP(y);
        dp[x]+=dp[y];
    }
    head[x]=0;
    dp[x]=min(dp[x],minn[x]);
}

int main(void)
{
    int n,m;
    int x,y,z;
    int k;
    scanf("%d",&n);
    t=log(n)/log(2)+1;

    for(int i=1;i<n;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);add(y,x,z);
    }
    minn[1]=lnf;
    dfs(1,0);

    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&k);
        build(k);
        DP(1);
        printf("%lld\n",dp[1]);
    }

    return 0;

}

例②:P4103 [HEOI2014]大工程:
题目描述
国家有一个大工程,要给一个非常大的交通网络里建一些新的通道。

我们这个国家位置非常特殊,可以看成是一个单位边权的树,城市位于顶点上。

在 2 个国家 a,b 之间建一条新通道需要的代价为树上 a,b 的最短路径。

现在国家有很多个计划,每个计划都是这样,我们选中了 k 个点,然后在它们两两之间 新建 C(k,2)条 新通道。现在对于每个计划,我们想知道: 1.这些新通道的代价和 2.这些新通道中代价最小的是多少 3.这些新通道中代价最大的是多少

输入格式
第一行 n 表示点数。

接下来 n-1 行,每行两个数 a,b 表示 a 和 b 之间有一条边。点从 1 开始标号。

接下来一行 q 表示计划数。对每个计划有 2 行,第一行 k 表示这个计划选中了几个点。

第二行用空格隔开的 k 个互不相同的数表示选了哪 k 个点。

输出格式
输出 q 行,每行三个数分别表示代价和,最小代价,最大代价。

输入输出样例
输入 #1 复制
10
2 1
3 2
4 1
5 2
6 4
7 5
8 6
9 7
10 9
5
2
5 4
2
10 4
2
5 2
2
6 1
2
6 1
输出 #1 复制
3 3 3
6 6 6
1 1 1
2 2 2
2 2 2
说明/提示
对于第 1,2 个点: n<=10000

对于第 3,4,5 个点: n<=100000,交通网络构成一条链

对于第 6,7 个点: n<=100000

对于第 8,9,10 个点: n<=1000000

对于所有数据, q<=50000并且保证所有k之和<=2*n

题目分析:对于每次询问,建立虚树。
总代价考虑贡献,最大最小代价dp转移就好啦。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<deque>
#include<map>
#include<vector>
#include<cmath>
#define ll long long
#define llu unsigned ll
using namespace std;
const double eps = 1e-8;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int maxn=1000010;
const int mod=1e9+7;
int hh[maxn],vv[maxn<<1],ee[maxn<<1],nn[maxn<<1];
int head[maxn],ver[maxn],nt[maxn];
int sum[maxn],d[maxn],f[maxn][22],s[maxn],dfn[maxn],a[maxn];
bool ha[maxn];
ll dis[maxn],maxx[maxn],minn[maxn];
int t,tt=1,tot=1,cnt=0,top=0;
int n,m;
int x,y,z;
int k;


void add(int x,int y,int z)
{
    vv[++tt]=y,ee[tt]=z;
    nn[tt]=hh[x],hh[x]=tt;
}

void add(int x,int y)
{
    ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}

bool cmp(const int &a,const int &b)
{
    return dfn[a]<dfn[b];
}


void dfs(int x,int fa)
{
    dfn[x]=++cnt;
    for(int i=hh[x];i;i=nn[i])
    {
        int y=vv[i],z=ee[i];
        if(y==fa) continue;
        d[y]=d[x]+1;
        f[y][0]=x;
        dis[y]=dis[x]+z;
        for(int j=1;j<=t;j++)
            f[y][j]=f[f[y][j-1]][j-1];
        dfs(y,x);
    }
}

int LCA(int x,int y)
{
    if(d[x]>d[y]) swap(x,y);
    for(int i=t;i>=0;i--)
        if(d[f[y][i]]>=d[x]) y=f[y][i];
    if(y==x) return x;
    for(int i=t;i>=0;i--)
        if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}

void in(int x)
{
    if(x==1) return ;
    if(top==1)
    {
        s[++top]=x;
        return ;
    }
    int lca=LCA(s[top],x);
    if(lca==s[top])
    {
        s[++top]=x;
        return ;
    }
    while(top>1&&dfn[s[top-1]]>=dfn[lca])
    {
        add(s[top-1],s[top]);
        top--;
    }
    if(lca!=s[top]) add(lca,s[top]),s[top]=lca;
    s[++top]=x;

}

void build(int k)
{
    for(int i=1;i<=k;i++)
        scanf("%d",&a[i]),ha[a[i]]=true;
    sort(a+1,a+k+1,cmp);

    s[top=1]=1;
    tot=1;
    for(int i=1;i<=k;i++)
        in(a[i]);
    while(top) add(s[top-1],s[top]),top--;
}

ll ans1,ans2,ans3;
void DP(int x)
{
    //叶子节点一定是 ha[x]=true的点。
    sum[x]=ha[x];maxx[x]=0;minn[x]=ha[x]?0:inf;

    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        ll z=dis[y]-dis[x];
        DP(y);
        ans1+=1ll*(k-sum[y])*sum[y]*z;
        if(sum[x])
        {
            ans2=min(ans2,minn[x]+z+minn[y]);
            ans3=max(ans3,maxx[x]+z+maxx[y]);
        }
        minn[x]=min(minn[x],minn[y]+z);
        maxx[x]=max(maxx[x],maxx[y]+z);
        sum[x]+=sum[y];
    }
    ha[x]=false;
    head[x]=0;
}

int main(void)
{

    scanf("%d",&n);
    t=log(n)/log(2)+1;

    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y,1);add(y,x,1);
    }

    dfs(1,0);

    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        ans1=0,ans2=lnf,ans3=-lnf;
        scanf("%d",&k);
        build(k);
        DP(1);
        printf("%lld %lld %lld\n",ans1,ans2,ans3);
    }

    return 0;

}