[BZOJ3611][Heoi2014]大工程
试题描述
国家有一个大工程，要给一个非常大的交通网络里建一些新的通道。
我们这个国家位置非常特殊，可以看成是一个单位边权的树，城市位于顶点上。
在 2 个国家 a,b 之间建一条新通道需要的代价为树上 a,b 的最短路径。
现在国家有很多个计划，每个计划都是这样，我们选中了 k 个点，然后在它们两两之间 新建 C(k,2)条 新通道。
现在对于每个计划，我们想知道：
1.这些新通道的代价和
2.这些新通道中代价最小的是多少
3.这些新通道中代价最大的是多少
输入
第一行 n 表示点数。
接下来 n-1 行，每行两个数 a,b 表示 a 和 b 之间有一条边。
点从 1 开始标号。 接下来一行 q 表示计划数。
对每个计划有 2 行，第一行 k 表示这个计划选中了几个点。
第二行用空格隔开的 k 个互不相同的数表示选了哪 k 个点。
输出
输出 q 行，每行三个数分别表示代价和，最小代价，最大代价。
输入示例
输出示例
数据规模及约定
n<=1000000
q<=50000并且保证所有k之和<=2*n
题解
建出虚树后恶心 dp。。。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
using namespace std; int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
} #define maxn 1000010
#define maxm 2000010
#define maxlog 20
#define oo 2147483647
#define LL long long
int n, m, head[maxn], next[maxm], to[maxm]; void AddEdge(int a, int b) {
to[++m] = b; next[m] = head[a]; head[a] = m;
swap(a, b);
to[++m] = b; next[m] = head[a]; head[a] = m;
return ;
} int ord[maxn], clo, dep[maxn], fa[maxlog][maxn];
void build(int u) {
ord[u] = ++clo;
for(int i = 1; i < maxlog; i++) fa[i][u] = fa[i-1][fa[i-1][u]];
for(int e = head[u]; e; e = next[e]) if(to[e] != fa[0][u]) {
fa[0][to[e]] = u;
dep[to[e]] = dep[u] + 1;
build(to[e]);
}
return ;
}
int lca(int a, int b) {
if(dep[a] < dep[b]) swap(a, b);
for(int i = maxlog - 1; i >= 0; i--) if(dep[a] - (1 << i) >= dep[b]) a = fa[i][a];
for(int i = maxlog - 1; i >= 0; i--) if(fa[i][a] != fa[i][b]) a = fa[i][a], b = fa[i][b];
return a == b ? a : fa[0][b];
} bool cmp(int a, int b) { return ord[a] < ord[b]; }
int ps[maxn], cp, psi[maxn], cpi, vis[maxn], siz[maxn], mn[maxn], mx[maxn], mn2[maxn], mx2[maxn];
bool flg[maxn];
LL f[maxn], sum[maxn];
int m2, h2[maxn], n2[maxm], t2[maxm], d2[maxm];
void Add2(int a, int b, int c) {
// printf("add2: %d %d %d\n", a, b, c);
t2[++m2] = b; d2[m2] = c; n2[m2] = h2[a]; h2[a] = m2;
swap(a, b);
t2[++m2] = b; d2[m2] = c; n2[m2] = h2[a]; h2[a] = m2;
return ;
}
void dp(int u, int pa) {
sum[u] = f[u] = siz[u] = 0;
mn[u] = oo; mx[u] = mx2[u] = 0;
if(flg[u]) mn2[u] = 0; else mn2[u] = oo;
for(int e = h2[u]; e; e = n2[e]) if(t2[e] != pa) {
dp(t2[e], u);
LL tmp = sum[t2[e]] + (LL)siz[t2[e]] * d2[e];
f[u] += sum[u] * siz[t2[e]] + tmp * siz[u] + f[t2[e]];
// printf("t2[e]: %d %lld %lld %d\n", t2[e], sum[u], tmp, siz[u]);
sum[u] += tmp;
siz[u] += siz[t2[e]];
mn[u] = min(mn[u], mn[t2[e]]);
if(mn2[t2[e]] < oo) {
if(mn2[u] < oo) mn[u] = min(mn[u], mn2[u] + mn2[t2[e]] + d2[e]);
mn2[u] = min(mn2[u], mn2[t2[e]] + d2[e]);
}
mx[u] = max(mx[u], mx[t2[e]]);
mx[u] = max(mx[u], mx2[u] + mx2[t2[e]] + d2[e]);
mx2[u] = max(mx2[u], mx2[t2[e]] + d2[e]);
}
f[u] += sum[u] * flg[u];
siz[u] += flg[u];
// printf("u: %d %d %lld %lld %d\n", u, pa, f[u], sum[u], siz[u]);
h2[u] = flg[u] = 0;
return ;
} int main() {
n = read();
for(int i = 1; i < n; i++) {
int a = read(), b = read();
AddEdge(a, b);
}
build(1);
// for(int i = 1; i <= n; i++) printf("%d%c", ord[i], i < n ? ' ' : '\n'); int q = read();
while(q--) {
cpi = read(); cp = 0;
for(int i = 1; i <= cpi; i++) {
psi[i] = read();
vis[psi[i]] = q + 1;
ps[++cp] = psi[i];
flg[ps[cp]] = 1;
}
sort(psi + 1, psi + cpi + 1, cmp);
int rt, dr = oo;
for(int i = 1; i < cpi; i++) {
int c = lca(psi[i], psi[i+1]);
if(dep[c] < dr) dr = dep[c], rt = c;
if(vis[c] != q + 1) vis[c] = q + 1, ps[++cp] = c;
}
sort(ps + 1, ps + cp + 1, cmp);
m2 = 0;
// for(int i = 1; i <= cp; i++) printf("%d%c", ps[i], i < cp ? ' ' : '\n');
for(int i = 1; i < cp; i++) {
int a = ps[i], b = ps[i+1], c = lca(a, b);
Add2(b, c, dep[b] - dep[c]);
}
dp(rt, 0);
printf("%lld %d %d\n", f[rt], mn[rt], mx[rt]);
} return 0;
}