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

Problem

【HEOI2014】大工程

Description

国家有一个大工程，要给一个非常大的交通网络里建一些新的通道。
我们这个国家位置非常特殊，可以看成是一个单位边权的树，城市位于顶点上。
在两个国家之间建一条新通道需要的代价为树上的最短路径。
现在国家有很多个计划，每个计划都是这样，我们选中了个点，然后在它们两两之间新建条新通道。
现在对于每个计划，我们想知道：

这些新通道的代价和
这些新通道中代价最小的是多少
这些新通道中代价最大的是多少

Input

第一行表示点数。
接下来行，每行两个数表示和之间有一条边。
点从开始标号。接下来一行表示计划数。
对每个计划有行，第一行表示这个计划选中了几个点。
第二行用空格隔开的个互不相同的数表示选了哪个点。

Output

输出行，每行三个数分别表示代价和，最小代价，最大代价。

Sample Input

Sample Output

HINT

，，保证

Source

鸣谢佚名上传

标签：虚树 DP

Solution

虚树裸题。

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

由于题目中有限制，考虑对每次询问的关键点建立虚树，在虚树上，即可将复杂度降低到线性级别。

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;
}