消耗战

Time Limit: 20 Sec Memory Limit: 512 MB

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行，每行一个整数ki，代表第i次后，有ki个岛屿资源丰富，接下来k个整数h1,h2,…hk，表示资源丰富岛屿的编号。

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

Main idea

给定一棵带权树，每次询问给出若干个关键节点，求出删去若干边使得关键节点无法到达根的最优方案。

Solution

显然想到了树形DP，但是直接做DP会TLE。

我们又发现了其实没有必要把全部边都走完，那么只要构建一棵虚树，在虚树上跑DP即可。

虚树构建方法：
　　1. 将关键点按照DFS序排序；
　　2. 求出排序后相邻两点的LCA（可以证明就是任意两点的LCA），和关键点一起按照DFS序排序，去重后得到虚树点集；
　　3. 用栈扫描一遍，维护从根到当前点的链（方法：如果栈顶是i的祖先，那么连边，加入i，否则弹栈）。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
#include<bits/stdc++.h>
using namespace std;

const int ONE=500001;
const int INF=2147483640;

int n,m,T;
int x,y,z;
int next1[ONE],first1[ONE],go1[ONE],w1[ONE],tot1;
int next[ONE],first[ONE],go[ONE],w[ONE],tot;
int size[250001],Rank[250001];
int dfn[250001],cnt,num;
int f[ONE][25],Dep[250001];
int Output[ONE];
int N;
long long dp[250001];
int Minedge[ONE];
int vis[250001];
int q[250001],top;

struct power
{
    int v;
    int rank;
}a[ONE];

int cmp(const power &a,const power &b)
{
    return a.rank<b.rank;
}

int rule(const power &a,const power &b)
{
    return (a.v==b.v && a.rank==b.rank);
}

int get()
{
    int res,Q=1;    char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

int Add(int u,int v,int z)
{
    next1[++tot1]=first1[u];    first1[u]=tot1; go1[tot1]=v;    w1[tot1]=z;
    next1[++tot1]=first1[v];    first1[v]=tot1; go1[tot1]=u;    w1[tot1]=z;
}

int New_Add(int u,int v,int z)
{
    next[++tot]=first[u];   first[u]=tot;   go[tot]=v;  w[tot]=z;
    next[++tot]=first[v];   first[v]=tot;   go[tot]=u;  w[tot]=z;
}

int Dfs(int u,int father)
{
    dfn[++cnt]=u;
    size[u]=1;
    Dep[u]=Dep[father]+1;
    for(int i=0;i<=19;i++)
    {
        f[u][i+1]=f[f[u][i]][i];
    }

    for(int e=first1[u];e;e=next1[e])
    {
        int v=go1[e];
        if(v==father) continue;
        f[v][0]=u;
        Minedge[v]=min(w1[e],Minedge[u]);
        Dfs(v,u);
        size[u]+=size[v];
    }
}

int LCA(int x,int y)
{
    if(Dep[x]<Dep[y]) swap(x,y);
    for(int i=20;i>=0;i--)
    {
        if(Dep[f[x][i]]>=Dep[y]) x=f[x][i];
        if(x==y) return x;
    }

    for(int i=20;i>=0;i--)
    {
        if(f[x][i]!=f[y][i])
        {
            x=f[x][i];
            y=f[y][i];
        }
    }

    return f[x][0];
}

int Check(int u,int v)
{
    if(Rank[u]<=Rank[v] && Rank[v]<=Rank[u]+size[u]-1) return 1;
    return 0;
}

void Deal()
{
    tot=0;
    for(int i=2;i<=num;i++)
    {
        int x=a[i].v;
        while(!Check(q[top],x)) top--;
        New_Add(q[top],x,Minedge[x]);
        q[++top]=x;
    }
}

void Tree_dp(int u,int father)
{
    dp[u]=0;
    for(int e=first[u];e;e=next[e])
    {
        int v=go[e];
        if(v==father) continue;
        Tree_dp(v,u);
        if(vis[v]) dp[u]+=w[e];
        else dp[u]+=min(dp[v],(long long)w[e]);
    }
    first[u]=0;
}

int main()
{
    n=get();
    for(int i=1;i<n;i++)
    {
        x=get();    y=get();    z=get();
        Add(x,y,z);
    }

    memset(Minedge,63,sizeof(Minedge));
    Dfs(1,0);
    Minedge[1]=0;
    for(int i=1;i<=cnt;i++) Rank[dfn[i]]=i;

    T=get();

    while(T--)
    {
        m=get();
        num=0;
        N=m;
        for(int i=1;i<=m;i++)
        {
            a[++num].v=get();
            a[num].rank=Rank[a[num].v];
            vis[a[num].v]=1;
        }

        sort(a+1,a+num+1,cmp);
        for(int i=2;i<=m;i++)
        {
            a[++num].v=LCA(a[i].v,a[i-1].v);
            a[num].rank=Rank[a[num].v];
        }

        a[++num].v=1; vis[1]=1;
        a[num].rank=1;

        sort(a+1,a+num+1,cmp);
        num=unique(a+1,a+num+1,rule)-1-a;

        top=0;  q[++top]=1;
        Deal();
        Tree_dp(1,0);

        printf("%lld\n",dp[1]);
        for(int i=1;i<=num;i++) a[i].rank=a[i].v=vis[a[i].v]=0;
    }

}