3611: [Heoi2014]大工程
Time Limit: 60 Sec Memory Limit: 512 MB
Submit: 408 Solved: 190
[Submit][Status][Discuss]
Description
国家有一个大工程，要给一个非常大的交通网络里建一些新的通道。
我们这个国家位置非常特殊，可以看成是一个单位边权的树，城市位于顶点上。
在 2 个国家 a,b 之间建一条新通道需要的代价为树上 a,b 的最短路径。
现在国家有很多个计划，每个计划都是这样，我们选中了 k 个点，然后在它们两两之间 新建 C(k,2)条 新通道。
现在对于每个计划，我们想知道：
1.这些新通道的代价和
2.这些新通道中代价最小的是多少
3.这些新通道中代价最大的是多少
Input
第一行 n 表示点数。
接下来 n-1 行，每行两个数 a,b 表示 a 和 b 之间有一条边。
点从 1 开始标号。 接下来一行 q 表示计划数。
对每个计划有 2 行，第一行 k 表示这个计划选中了几个点。
第二行用空格隔开的 k 个互不相同的数表示选了哪 k 个点。
Output
输出 q 行，每行三个数分别表示代价和，最小代价，最大代价。
Sample Input
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
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
Sample Output
3 3 3
6 6 6
1 1 1
2 2 2
2 2 2
6 6 6
1 1 1
2 2 2
2 2 2
HINT
n<=1000000
q<=50000并且保证所有k之和<=2*n
Source
【思路】
虚树+树上DP
对每次询问构造虚树，在虚树上进行DP。
ans1和ans2即树上的最长/短链问题，利用前缀和思想可以求解。
设sum[x] = ∑(sum[y] + w * size[y]); 则有
ans += ∑((sum[y] + w * size[y]) * (size[x] - size[y]));
其中size[x]表示以x为根的子树包含的询问点数目,w为x->y的边长。
好大的工程=-=
【代码】
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std; const int N = +;
const int INF = 1e9+1e9;
const int D = ; typedef long long LL;
vector<int> G[N],g[N];
int d[N],dfn[N];
int n,q,dfsc; void adde(int u,int v) {
if(u!=v) G[u].push_back(v); else return;
}
bool cmp(const int& lhs,const int& rhs) {
return dfn[lhs]<dfn[rhs];
}
////////////////////////////////////////////////////lca which cuts down about 5000ms
int siz[N],top[N],son[N],fa[N];
void dfs1(int u) {
siz[u]=,son[]=; dfn[u]=++dfsc;
for(int i=;i<g[u].size();i++) {
int v=g[u][i];
if(v!=fa[u]) {
fa[v]=u; d[v]=d[u]+;
dfs1(v);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
}
}
void dfs2(int u,int tp) {
top[u]=tp;
if(son[u]) dfs2(son[u],tp);
for(int i=;i<g[u].size();i++) {
int v=g[u][i];
if(v!=son[u] && v!=fa[u]) dfs2(v,v);
}
}
int LCA(int u,int v) {
while(top[u]!=top[v])
if(d[top[u]]>=d[top[v]]) u=fa[top[u]];
else v=fa[top[v]];
return d[u]<d[v]? u:v;
}
////////////////////////////////////////////////
LL sum[N],ans;
int ans1,ans2,mi[N],mx[N],sz[N]; bool ifq[N];
int dp(int u) {
sum[u]=; sz[u]=ifq[u];
mi[u]=ifq[u]? :INF;
mx[u]=ifq[u]? :-INF;
for(int i=;i<G[u].size();i++) {
int v=G[u][i],w=d[v]-d[u];
dp(v);
sz[u]+=sz[v];
sum[u]+=sum[v]+sz[v]*w;
ans1=min(ans1,mi[u]+mi[v]+w);
ans2=max(ans2,mx[u]+mx[v]+w);
mi[u]=min(mi[u],mi[v]+w);
mx[u]=max(mx[u],mx[v]+w);
}
for(int i=;i<G[u].size();i++) {
int v=G[u][i],w=d[v]-d[u];
ans+=(sum[v]+sz[v]*w)*(sz[u]-sz[v]);
}
ifq[u]=; G[u].clear(); //clear
}
void read(int& x) {
char c=getchar();while(!isdigit(c))c=getchar();
x=;while(isdigit(c))x=x*+c-'' , c=getchar();
}
void solve() {
int tot=,top=,k;
static int st[N],h[N];
read(k);
for(int i=;i<=k;i++) read(h[i]),ifq[h[i]]=;
sort(h+,h+k+,cmp);
st[++top]=;
for(int i=;i<=k;i++) {
int p=h[i],lca=LCA(p,st[top]);
for(;;) {
if(d[lca]>=d[st[top-]]) {
adde(lca,st[top]);
top--;
if(st[top]!=lca) st[++top]=lca;
break;
}
adde(st[top-],st[top]); top--;
}
if(st[top]!=p) st[++top]=p;
}
while(--top) adde(st[top],st[top+]);
ans=ans2= , ans1=INF;
dp();
printf("%lld %d %d\n",ans,ans1,ans2);
}
int main() {
read(n);
int u,v;
for(int i=;i<n;i++) {
read(u),read(v);
g[u].push_back(v) , g[v].push_back(u);
}
d[]=; dfs1(); dfs2(,);
read(q);
while(q--) solve();
return ;
}