BZOJ 2286: [Sdoi2011]消耗战

2286: [Sdoi2011消耗战

Time Limit: 20 Sec  Memory Limit: 512 MB
Submit: 2082  Solved: 736
[Submit][Status][Discuss]

Description

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

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

Input

第一行一个整数n，代表岛屿数量。

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

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

接下来m行，每行一个整数k_i，代表第i次后，有k_i个岛屿资源丰富，接下来k个整数h₁,h₂,…h_k，表示资源丰富岛屿的编号。

Output

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

 

Sample Input

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

Sample Output

12
32
22

HINT

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

Source

Stage2 day2

---

虚树入门题，如果你想知道虚树如何构造：http://user.qzone.qq.com/872191552/main

DP

记dis[i]为点i到根节点的路径中最小的边的权值

f[i]=min(dis[i],sigma f[son[i]]);

---

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<stack>
#define maxn 500100
#define llg long long
using namespace std;
struct node
{
    llg df,po;
}d[maxn];
llg i,j,k,n,m,p[maxn][22],dad[maxn],bj[maxn],dfs[maxn],cnt,T,deep[maxn],dis[maxn],se[maxn],q,ss[maxn],open,dl[maxn];
vector <llg> a[maxn],c[maxn],val[maxn];
stack <llg> z;


inline int getint(){
    char c=getchar(); llg w=0,q=0;
    while(c!='-' && ( c<'0' || c>'9')) c=getchar();
    if(c=='-') c=getchar(),q=1;
    while(c>='0' && c<='9') w=w*10+c-'0',c=getchar();
    return q?-w:w;
}

void link(llg x,llg y,llg z) {a[x].push_back(y); val[x].push_back(z); val[y].push_back(z); a[y].push_back(x);}

void link_(llg x,llg y) {c[x].push_back(y); c[y].push_back(x);}

bool cmp(const node&a,const node&b){return a.df<b.df;}

void find_dad_deep(llg x,llg di)
{
    bj[x]=1; dfs[x]=++cnt; dis[x]=di;
    llg w=a[x].size();
    for (llg i=0;i<w;i++)
        if (!bj[a[x][i]])
            {
                dad[a[x][i]]=x; p[a[x][i]][0]=x; deep[a[x][i]]=deep[x]+1;
                find_dad_deep(a[x][i],min(di,val[x][i]));
            }
}

void build_lca()
{
    for (i=1;(2<<i)<=n;i++)
        for (j=1;j<=n;j++)
            p[j][i]=p[p[j][i-1]][i-1];
}

llg lca(llg x,llg y)
{
    if (deep[x]<deep[y]) swap(x,y);
    for (llg i=18;i>=0;i--) if (deep[p[x][i]]>=deep[y]) x=p[x][i];
    if (x==y) return x;
    for (llg i=18;i>=0;i--)
        if (p[x][i]!=p[y][i]) {x=p[x][i]; y=p[y][i];}
    return dad[x];
}

llg st[maxn],top;

void make_tree(llg x)
{
    llg L=0,g1,g2;
    while(top)
        {
            g1=st[top];g2=st[top-1];L=lca(g1,x);
            if(deep[g2]>deep[L]) link_(g2,g1),top--;
            else if(deep[g2]<deep[L]) {link_(g1,L);top--;break;}
            else break;
        }
    if(st[top]!=L) st[++top]=L;        
    st[++top]=x;
}

void ceshi()
{
    for (llg i=1;i<=n;i++)
        {
            llg w=c[i].size();
            for (llg j=0;j<w;j++) if (i<c[i][j]) cout<<i<<" "<<c[i][j]<<endl;
        }
}

llg dp(llg x)
{
    bj[x]=1;
    dl[++open]=x;
    llg w=c[x].size(),tot=0;
    for (llg i=0;i<w;i++)
        if (!bj[c[x][i]])
            tot+=dp(c[x][i]);
    if (ss[x]) return dis[x];
    return min(tot,dis[x]);
}

int main()
{
    freopen("a.in","r",stdin); freopen("a.out","w",stdout);
    cin>>n;
    for (i=1;i<n;i++)
        {
            llg x,y,z;
            x=getint(),y=getint(),z=getint();
            link(x,y,z);
        }
    deep[1]=1;
    llg ggg=(llg)1e60;
    find_dad_deep(1,ggg); //dis[1]=0;
    build_lca();
    cin>>T; for (i=1;i<=n;i++) bj[i]=0;
    while (T--)
        {
            m=getint();
            llg x;
            for (i=1;i<=open;i++) {ss[se[i]]=0; c[dl[i]].clear(); bj[dl[i]]=0;}
            q=0,open=0;
            c[1].clear(); bj[1]=0; ss[1]=0;
            for (i=1;i<=m;i++) {x=getint(); d[i].po=x; d[i].df=dfs[x]; q++; ss[x]=1; se[q]=x; }
            sort(d+1,d+m+1,cmp);
            top=0;
            if (d[1].po!=1) st[++top]=1;
            for (i=1;i<=m;i++) make_tree(d[i].po);
            while(top!=1) link_(st[top],st[top-1]),top--;
            //if (q<=0) printf("0
"); else
            printf("%lld
",dp(1));
            //ceshi();
            //cout<<endl;
        }
    return 0;
}