【BZOJ2286】【SDOI2011】消耗战

我好像并没有写过虚树的题

然而我™为什么出过一道虚树题啊

那么作为虚树第一题还是讲一下虚树吧

虚树就是把所有的询问结点和他们两两的LCA取出新建一棵树，边权替换后再在上面进行dp等操作

具体实现可以将所有点按照dfs序排序，相邻的求LCA并加入，再去重，一定可以满足条件

连边的话就再按dfs序排序，建一个栈，每次不断将栈顶不为当前点的父辈的点弹出，直到是父辈节点，从栈顶向这个点连一条边，再将这个点丢进栈里即可

这题的dp还是比较简单的

// <2286.cpp> - 01/10/17 11:29:41
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int gi(){
    int res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
const int MAXN=250010;
const int MAXM=500010;
const int K=20;
const lol INF=1e17;
int bt,b[MAXN],next[MAXM],to[MAXM],val[MAXM];
inline void add(int x,int y,int z){
    next[++bt]=b[x];b[x]=bt;to[bt]=y;val[bt]=z;
    next[++bt]=b[y];b[y]=bt;to[bt]=x;val[bt]=z;
}
inline void add(int x,int y){next[++bt]=b[x];b[x]=bt;to[bt]=y;}
int tot,dfn[MAXN],end[MAXN],f[K][MAXN],dep[MAXN];
lol v[MAXN];
void dfs(int x){
    dfn[x]=++tot;
    for(int i=b[x];i;i=next[i]){
        if(to[i]==f[0][x])continue;
        f[0][to[i]]=x;
        dep[to[i]]=dep[x]+1;
        v[to[i]]=min(v[x],lol(val[i]));
        dfs(to[i]);
    }
    end[x]=tot;
}
int cmp(int x,int y){return dfn[x]<dfn[y];}
int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    int d=dep[x]-dep[y];
    for(int i=0,p=1;i<K;i++,p<<=1)
        if(d&p)x=f[i][x];
    if(x==y)return x;
    for(int i=K-1;i>=0;i--){
        if(f[i][x]==f[i][y])continue;
        x=f[i][x];y=f[i][y];
    }
    return f[0][x];
}
int a[MAXN],s[MAXN];
bool y[MAXN];
lol dp(int x){
    if(y[x])return v[x];
    lol r=0;
    for(int i=b[x];i;i=next[i])r+=dp(to[i]);
    return min(r,v[x]);
}
int main(){
    int n=gi();
    for(int i=1;i<n;i++){
        int u=gi(),v=gi(),w=gi();
        add(u,v,w);
    }
    v[1]=INF;dfs(1);
    for(int j=1;j<K;j++)
        for(int i=1;i<=n;i++)f[j][i]=f[j-1][f[j-1][i]];
    int m=gi();
    while(m--){
        int k=gi(),l=k;
        for(int i=1;i<=k;i++)y[a[i]=gi()]=1;
        sort(a+1,a+k+1,cmp);
        for(int i=1;i<l;i++)a[++k]=lca(a[i],a[i+1]);a[++k]=1;
        sort(a+1,a+k+1,cmp);
        k=unique(a+1,a+k+1)-a-1;
        int t=0;bt=0;
        for(int i=1;i<=k;i++){
            b[a[i]]=0;
            while(t&&(dfn[a[i]]<dfn[s[t]]||end[s[t]]<dfn[a[i]]))t--;
            add(s[t],a[i]);
            s[++t]=a[i];
        }
        printf("%lld\n",dp(1));
        for(int i=1;i<=k;i++)y[a[i]]=0;
    }
    return 0;
}

// <2286.cpp> - 01/10/17 11:29:41

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int gi(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=250010;

const int MAXM=500010;

const int K=20;

const lol INF=1e17;

int bt,b[MAXN],next[MAXM],to[MAXM],val[MAXM];

inline void add(int x,int y,int z){

next[++bt]=b[x];b[x]=bt;to[bt]=y;val[bt]=z;

next[++bt]=b[y];b[y]=bt;to[bt]=x;val[bt]=z;

}

inline void add(int x,int y){next[++bt]=b[x];b[x]=bt;to[bt]=y;}

int tot,dfn[MAXN],end[MAXN],f[K][MAXN],dep[MAXN];

lol v[MAXN];

void dfs(int x){

dfn[x]=++tot;

for(int i=b[x];i;i=next[i]){

if(to[i]==f[0][x])continue;

f[0][to[i]]=x;

dep[to[i]]=dep[x]+1;

v[to[i]]=min(v[x],lol(val[i]));

dfs(to[i]);

}

end[x]=tot;

}

int cmp(int x,int y){return dfn[x]<dfn[y];}

int lca(int x,int y){

if(dep[x]<dep[y])swap(x,y);

int d=dep[x]-dep[y];

for(int i=0,p=1;i<K;i++,p<<=1)

if(d&p)x=f[i][x];

if(x==y)return x;

for(int i=K-1;i>=0;i--){

if(f[i][x]==f[i][y])continue;

x=f[i][x];y=f[i][y];

}

return f[0][x];

}

int a[MAXN],s[MAXN];

bool y[MAXN];

lol dp(int x){

if(y[x])return v[x];

lol r=0;

for(int i=b[x];i;i=next[i])r+=dp(to[i]);

return min(r,v[x]);

}

int main(){

int n=gi();

for(int i=1;i<n;i++){

int u=gi(),v=gi(),w=gi();

add(u,v,w);

}

v[1]=INF;dfs(1);

for(int j=1;j<K;j++)

for(int i=1;i<=n;i++)f[j][i]=f[j-1][f[j-1][i]];

int m=gi();

while(m--){

int k=gi(),l=k;

for(int i=1;i<=k;i++)y[a[i]=gi()]=1;

sort(a+1,a+k+1,cmp);

for(int i=1;i<l;i++)a[++k]=lca(a[i],a[i+1]);a[++k]=1;

sort(a+1,a+k+1,cmp);

k=unique(a+1,a+k+1)-a-1;

int t=0;bt=0;

for(int i=1;i<=k;i++){

b[a[i]]=0;

while(t&&(dfn[a[i]]<dfn[s[t]]||end[s[t]]<dfn[a[i]]))t--;

add(s[t],a[i]);

s[++t]=a[i];

}

printf("%lld\n",dp(1));

for(int i=1;i<=k;i++)y[a[i]]=0;

}

return 0;

}