BZOJ3611【HEOI2014】大工程 < 虚树+DP >

Problem

【HEOI2014】大工程

$\mathrm{Time\;Limit:\;60\;Sec}$
$\mathrm{Memory\;Limit:\;512\;MB}$

Description

国家有一个大工程，要给一个非常大的交通网络里建一些新的通道。
我们这个国家位置非常特殊，可以看成是一个单位边权的树，城市位于顶点上。
在两个国家$a,b$之间建一条新通道需要的代价为树上$a,b$的最短路径。
现在国家有很多个计划，每个计划都是这样，我们选中了$k$个点，然后在它们两两之间新建$\binom{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

Sample Output

3 3 3
6 6 6
1 1 1
2 2 2
2 2 2

HINT

$n\le10^6$，$q\le5\times10^4$，保证$\sum k\le2\cdot n$

Source

鸣谢佚名上传

标签：虚树 DP

Solution

虚树$\mathrm{DP}$裸题。

不考虑时间复杂度，可以直接对于每次询问树形$\mathrm{DP}$一遍，统计每条边的贡献，对于每个点记录其到子树中关键点的最长链，并在选中的点上将最长/短的两条到关键点的链拼接即可得到全局最长/短链。这样每次$\mathrm{DP}$是$O(n)$的，总复杂度$O(n^2)$。

由于题目中有限制$\sum k\le 2\cdot n$，考虑对每次询问的关键点建立虚树，在虚树上$\mathrm{DP}$，即可将复杂度降低到线性级别。

Code

#include <bits/stdc++.h>
#define LOG 20
#define MAX_N 1000000
#define INF 0x3f3f3f3f
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, q, fa[MAX_N+5][LOG+1];
int ind, dfn[MAX_N+5], dep[MAX_N+5];
vector <int> G[MAX_N+5], T[MAX_N+5];
int sz[MAX_N+5]; bool mrk[MAX_N+5];
vector <int> p; int s[MAX_N+5], tp;
lnt tot; int mi, mx, f[MAX_N+5], g[MAX_N+5];
bool cmp (const int &a, const int &b) {return dfn[a] < dfn[b];}
void DFS(int u) {
    dfn[u] = ++ind, dep[u] = dep[fa[u][0]]+1;
    for (int i = 1; i <= LOG; i++)
        fa[u][i] = fa[fa[u][i-1]][i-1];
    for (int i = 0, v; i < (int)G[u].size(); i++)
        if ((v = G[u][i]) ^ fa[u][0]) fa[v][0] = u, DFS(v);
}
int LCA(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = LOG; ~i; i--)
        if (dep[u]-(1<<i) >= dep[v]) u = fa[u][i];
    if (u == v) return u;
    for (int i = LOG; ~i; i--)
        if (fa[u][i] ^ fa[v][i])
            u = fa[u][i], v = fa[v][i];
    return fa[u][0];
}
void DP(int u) {
    sz[u] = mrk[u], f[u] = INF, g[u] = 0;
    for (int i = 0; i < (int)T[u].size(); i++) {
        int v = T[u][i], l = dep[v]-dep[u];
        DP(v), sz[u] += sz[v], tot += 1LL*sz[v]*(m-sz[v])*l;
        mi = min(mi, f[u]+f[v]+l), mx = max(mx, g[u]+g[v]+l);
        f[u] = min(f[u], f[v]+l), g[u] = max(g[u], g[v]+l);
    }
    if (mrk[u]) mi = min(mi, f[u]), mx = max(mx, g[u]);
    if (mrk[u]) f[u] = 0; T[u].clear(), mrk[u] = false;
}
int main() {
    read(n);
    for (int i = 1, u, v; i < n; i++)
        read(u), read(v), G[u].push_back(v), G[v].push_back(u);
    DFS(1), read(q);
    while (q--) {
        read(m), p.clear(), tp = 0;
        for (int i = 0, x; i < m; i++)
            read(x), p.push_back(x), mrk[x] = true;
        sort(p.begin(), p.end(), cmp);
        for (int i = 0; i < m; i++)
            if (!tp) s[++tp] = p[i];
            else {
                int lca = LCA(p[i], s[tp]);
                while (dfn[lca] < dfn[s[tp]])
                    if (dfn[lca] >= dfn[s[tp-1]]) {
                        T[lca].push_back(s[tp]);
                        if (s[--tp] ^ lca) s[++tp] = lca;
                    } else T[s[tp-1]].push_back(s[tp]), tp--;
                s[++tp] = p[i];
            }
        while (tp > 1) T[s[tp-1]].push_back(s[tp]), tp--;
        mi = INF, mx = 0, tot = 0; DP(s[tp]);
        printf("%lld %d %d\n", tot, mi, mx);
    }
    return 0;
}