bzoj 2286 [Sdoi2011]消耗战（虚树+树上DP）

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

【题目链接】

http://www.lydsy.com/JudgeOnline/problem.php?id=2286

【题意】

给定一棵树，切断一条树边代价为ci，有m个询问，每次问使得1号点与查询的k个点不连通的最小代价。

【思路】

虚树+树上DP。

构建虚树，这里学了一个比较机智的构图方法：当询问点之间存在子孙后代关系时只保留最上面的节点。

在这种构图方式的基础上进行树上DP，设f[u]表示以u为根的子树，则有转移式：

f[u]=min{mn[u] , sum(f[v])},u不是资源点

f[u]=mn[u],u是资源点

其中mn[u]表示u到根的路径上的最短边。Ps：每个叶子都代表一个询问点，第二个抉择只是为了提供最短边都在u之下的情况，如果在u之上虽然会出现费用计算重合但这不是最优解所以无关紧要。

需要注意的是mx[1]赋大值，d[1]设为1，对应清空边表而非一次n的循环。另外vector中的clear()并不是释放空间，可以看作形如size=0的操作，所以不用担心初始化时间的问题。

LCA好像写得有点挫，效率不是很高的样子=-=

【代码】

#include<cstdio>
#include<cstring>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std; typedef long long LL;
const int N = +;
const int D = ; struct Edge{ int u,v,w;
};
vector<Edge> es;
vector<int> g[N],G[N];
int fa[N][D],d[N],dfn[N],bin[D]; LL mx[N];
int n,m,dfsc; void adde(int u,int v,int w) {
es.push_back((Edge){u,v,w});
int m=es.size(); g[u].push_back(m-);
}
void adde2(int u,int v) {
if(u!=v) G[u].push_back(v); else return ;
//printf("es(%d,%d)\n",u,v);
}
bool cmp(const int& lhs,const int& rhs) { return dfn[lhs]<dfn[rhs];
} void dfs(int u) {
dfn[u]=++dfsc;
for(int i=;i<g[u].size();i++) {
Edge e=es[g[u][i]]; int v=e.v;
if(v!=fa[u][]) {
fa[v][]=u;
for(int j=;j<D;j++) fa[v][j]=fa[fa[v][j-]][j-];
d[v]=d[u]+; mx[v]=min(mx[u],(LL)e.w);
dfs(v);
}
}
}
int LCA(int u,int v) {
if(d[v]>d[u]) swap(u,v);
for(int i=D-;i>=;i--)
if(d[fa[u][i]]>=d[v]) u=fa[u][i];
if(u==v) return u;
for(int i=D-;i>=;i--)
if(fa[u][i]!=fa[v][i]) u=fa[u][i] , v=fa[v][i];
return fa[u][];
}
void read(int &x) {
char c=getchar(); while(!isdigit(c)) c=getchar();
x=; while(isdigit(c)) x=x*+c-'' , c=getchar();
}
LL f[N];
void dp(int u) {
LL tmp=;
for(int i=;i<G[u].size();i++) {
dp(G[u][i]);
tmp += f[G[u][i]];
}
G[u].clear(); //清空边表
f[u]=mx[u]; //f=mx 所以mx赋大值
if(tmp && tmp<f[u]) f[u]=tmp;
}
void solve() {
int top=,tot=,k;
static int st[N],h[N];
read(k);
for(int i=;i<=k;i++) read(h[i]) ;
sort(h+,h+k+,cmp);
///////////////////////////////////// 以下是一个十分机智的重新构图 from hzwer
h[++tot]=h[];
for(int i=;i<=k;i++)
if(LCA(h[tot],h[i])!=h[tot]) h[++tot]=h[i]; //虚树中不会出现询问点间的子孙后代关系
st[++top]=;
for(int i=;i<=tot;i++) {
int p=h[i],lca=LCA(p,st[top]);
for(;;) {
if(d[st[top-]]<=d[lca]) {
adde2(lca,st[top--]);
if(st[top]!=lca) st[++top]=lca;
break;
}
adde2(st[top-],st[top]); top--;
}
if(st[top]!=p) st[++top]=p;
}
while(--top) adde2(st[top],st[top+]);
/////////////////////////////////////
dp();
printf("%lld\n",f[]);
} int main() {
read(n);
int u,v,w;
for(int i=;i<n-;i++) {
read(u),read(v),read(w);
adde(u,v,w) , adde(v,u,w);
}
mx[]=1e18,d[]=; dfs(); //d[1]=1
read(m);
while(m--) solve();
return ;
}