首页 > 代码库 > bzoj3611 [Heoi2014]大工程
bzoj3611 [Heoi2014]大工程
传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3611
【题解】
和bzoj2286一样,建虚树出来,在虚数上dp。
第一问分别考虑每条边的贡献即可。
第二问和第三问dp。
f[x][0/1],g[x][0/1]表示x子树,两个端点都在子树内/一个端点在子树内的max/min
转移随便讨论讨论
只是有点儿麻烦。。
第一问没longlong。。WA了好久qwq
# include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 2e6 + 10; const int mod = 1e9+7; # define RG register # define ST static int n; struct Graph { int n, head[M], nxt[M], to[M], w[M], tot; inline void set(int _n) { n = _n; tot = 0; for (int i=1; i<=n; ++i) head[i] = 0; } inline void add(int u, int v, int _w) { ++tot; nxt[tot] = head[u]; head[u] = tot; to[tot] = v; w[tot] = _w; } inline void adde(int u, int v, int _w=0) { add(u, v, _w); add(v, u, _w); } }G, T; int fa[M][21], dep[M], dfn[M], DFN=0; inline void dfs(int x, int father=0) { dfn[x] = ++DFN; for (int i=1; i<=20; ++i) fa[x][i] = fa[fa[x][i-1]][i-1]; for (int i=G.head[x]; i; i=G.nxt[i]) { if(G.to[i] == father) continue; fa[G.to[i]][0] = x; dep[G.to[i]] = dep[x] + 1; dfs(G.to[i], x); } } inline int lca(int u, int v) { if(dep[u] < dep[v]) swap(u, v); for (int i=20; ~i; --i) if((dep[u] - dep[v]) & (1<<i)) u = fa[u][i]; if(u == v) return u; for (int i=20; ~i; --i) if(fa[u][i] != fa[v][i]) { u = fa[u][i]; v = fa[v][i]; } return fa[u][0]; } inline int getdis(int u, int v) { int d = 0; if(dep[u] < dep[v]) swap(u, v); for (int i=20; ~i; --i) if((dep[u] - dep[v]) & (1<<i)) { u = fa[u][i]; d += (1<<i); } if(u == v) return d; for (int i=20; ~i; --i) if(fa[u][i] != fa[v][i]) { u = fa[u][i]; v = fa[v][i]; d += (1<<i)*2; } return d + 2; } inline void Tadd(int u, int v) { // printf("%d->%d\n", u, v); T.adde(u, v, getdis(u, v)); } ll ans = 0; int sz[M]; bool g[M]; int m, a[M], st[M], stn; inline void predp(int x, int father=0) { int wfa = 0; sz[x] = g[x]; for (int i=T.head[x]; i; i=T.nxt[i]) { int y = T.to[i]; if(y == father) { wfa = T.w[i]; continue; } predp(y, x); sz[x] += sz[y]; } if(father != 0) { // x->father ans += 1ll * wfa * sz[x] * (m-sz[x]); } } //f: min, h:max // first: all-in, second: one-out pair<int, int> f[M], h[M]; inline void dp(int x, int father=0) { f[x] = make_pair(1e9, 1e9); h[x] = make_pair(-1, -1); int ffir = 1e9, fsec = 1e9, hfir = -1, hsec = -1; for (int i=T.head[x], tem; i; i=T.nxt[i]) { int y = T.to[i]; if(y == father) continue; dp(y, x); if(f[y].second != 1e9) { tem = f[y].second + T.w[i]; f[x].second = min(f[x].second, tem); if(tem < ffir) fsec = ffir, ffir = tem; else if(tem < fsec) fsec = tem; } f[x].first = min(f[x].first, f[y].first); if(h[y].second != -1) { tem = h[y].second + T.w[i]; h[x].second = max(h[x].second, tem); if(tem > hfir) hsec = hfir, hfir = tem; else if(tem > hsec) hsec = tem; } h[x].first = max(h[x].first, h[y].first); } if(g[x]) { // is a dot f[x].second = min(f[x].second, 0); h[x].second = max(h[x].second, 0); f[x].first = min(f[x].first, ffir); if(hfir != -1) { if(hsec == -1) h[x].first = max(h[x].first, hfir); else h[x].first = max(h[x].first, hfir + hsec); } } else { f[x].first = min(f[x].first, ffir + fsec); if(hfir != -1 && hsec != -1) h[x].first = max(h[x].first, hfir + hsec); } T.head[x] = 0; } inline bool cmp_dfn(int x, int y) { return dfn[x] < dfn[y]; } inline void sol() { // puts("===="); ans = 0; scanf("%d", &m); for (int i=1; i<=m; ++i) scanf("%d", &a[i]); if(m == 0 || m == 1) { puts("0 0 0"); return ; } sort(a+1, a+m+1, cmp_dfn); for (int i=1; i<=m; ++i) g[a[i]] = 1; stn = 0; T.tot = 0; st[++stn] = 1; for (int i=1; i<=m; ++i) { if(a[i] == 1) continue; int LCA = lca(st[stn], a[i]); while(stn && dep[st[stn]] > dep[LCA]) { if(stn > 1) { if(dep[st[stn-1]] > dep[LCA]) Tadd(st[stn-1], st[stn]); else Tadd(st[stn], LCA); } --stn; } if(st[stn] != LCA) st[++stn] = LCA; st[++stn] = a[i]; } while(stn > 1) { Tadd(st[stn], st[stn-1]); --stn; } predp(1); dp(1); printf("%lld %d %d\n", ans, f[1].first, h[1].first); for (int i=1; i<=m; ++i) g[a[i]] = 0; } int main() { cin >> n; for (int i=1, u, v; i<n; ++i) { scanf("%d%d", &u, &v); G.adde(u, v); } dep[1] = 1; dfs(1); int Q; cin >> Q; while(Q--) sol(); return 0; }
bzoj3611 [Heoi2014]大工程
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。