Pre
开始的时候不叫 \(O2\) 的话 \(60\) 分，加了 \(O2\) 就 \(50\) 分。。。
Solution
直接虚树，本文目的在于说明易错点。
Code
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <limits.h>
#define ll long long
using namespace std;
struct _in {
const _in operator , (ll & a) const {
a = 0;
char k = getchar ();
while (k > '9' || k < '0') k = getchar ();
while (k >= '0' && k <= '9') {
a = a * 10 + k - '0';
k = getchar ();
}
return * this;
}
}in;
inline void swap (int&u, int&v) {
int c = u;
u = v,
v = c;
}
inline int min (int u, int v) {
return u > v ? v : u;
}
inline ll min (ll u, ll v) {
return u > v ? v : u;
}
const int N = 250000 + 5;
int n, dfn[N], dftot;
int m, dep[N], st[N][20];
ll sts[N][20], cnt, k[N];
bool cmp (int u, int v) {
return dfn[u] < dfn[v];
}
struct ECH {
int tme[N], now;
bool rch[N];
inline void init () {
++now;
}
inline void insert (int p) {
tme[p] = now, rch[p] = 1;
}
inline bool query (int p) {
if (tme[p] != now) tme[p] = now, rch[p] = 0;
else return rch[p];
return 0;
}
}rch;
struct Graph {
int fr[N << 1], to[N << 1], h[N], tot;
ll val[N << 1];
inline void add (int u, int v, ll w) {
tot++;
fr[tot] = h[u];
to[tot] = v;
h[u] = tot;
val[tot] = w;
}
inline void dfs (int u, int f) {
dfn[u] = ++dftot;
dep[u] = dep[f] + 1;
st[u][0] = f;
for (int i = 1; i <= 18; ++i) st[u][i] = st[ st[u][i - 1] ][i - 1];
for (int i = 1; i <= 18; ++i) sts[u][i] = min (sts[u][i - 1], sts[ st[u][i - 1] ][i - 1]);
for (int i = h[u]; i; i = fr[i]) {
if (to[i] == f) continue;
sts[ to[i] ][0] = val[i];
dfs (to[i], u);
}
}
inline int lca (int u, int v) {
if (dep[u] < dep[v]) swap (u, v);
for (int i = 19; i >= 0 && dep[u] != dep[v]; --i)
if (dep[ st[u][i] ] >= dep[v]) u = st[u][i];
for (int i = 19; i >= 0; --i)
if (st[u][i] != st[v][i]) u = st[u][i], v = st[v][i];
if (u == v) return u;
else return st[u][0];
}
inline ll query (int u, int v) {
ll res = INT_MAX;
if (dep[u] < dep[v]) swap (u, v);
for (int i = 18; i >= 0 && u != v; --i)
if (st[u][i] != v) res = min (res, sts[u][i]), u = st[u][i];
if (u != v) res = min (res, sts[u][0]);
return res;
}
}g1;
struct Graph2 {
int stk[N], top;
ll dp[N];
inline void init () {
top = 0;
}
inline void build () {
for (int i = 1; i <= cnt; ++i) {
dp[ k[i] ] = 0;
int v = k[i];
if (!top) { stk[++top] = v; continue; }
else {
int lca = g1.lca (v, stk[top]);
if (lca == stk[top]) {
stk[++top] = v;
continue;
}
while (1) {
if (dep[lca] > dep[ stk[top - 1] ]) {
dp[lca] = 0;
ll wt = g1.query(lca, stk[top]);
if (rch.query(stk[top])) dp[lca] += wt;
else dp[lca] += min (wt, dp[stk[top]]);
stk[top] = lca, stk[++top] = v;
break;
}
else if (dep[lca] == dep[ stk[top - 1] ]) {
ll wt = g1.query(lca, stk[top]);
if (rch.query(stk[top])) dp[lca] += wt;
else dp[lca] += min (wt, dp[stk[top]]);
stk[top] = v;
break;
}
else {
ll wt = g1.query(stk[top - 1], stk[top]);
if (rch.query(stk[top])) dp[ stk[top - 1] ] += wt;
else dp[ stk[top - 1] ] += min (wt, dp[ stk[top] ]);
top--;
}
}
}
}
while (top > 1) {
ll wt = g1.query(stk[top], stk[top - 1]);
if (rch.query(stk[top])) dp[ stk[top - 1] ] += wt;
else dp[ stk[top - 1] ] += min (wt, dp[ stk[top] ]);
--top;
}
}
}g2;
int main () {
memset (sts, 127, sizeof (sts));
scanf ("%d", &n);
for (int i = 1; i < n; ++i) {
ll x, y, z;
in, x, y, z;
g1.add (x, y, z), g1.add (y, x, z);
}
g1.dfs (1, 0);
scanf ("%d", &m);
while (m--) {
in, cnt;
rch.init ();
for (int i = 1; i <= cnt; ++i)
{ in, k[i]; rch.insert( k[i] ); }
k[++cnt] = 1;
sort (k + 1, k + cnt + 1, cmp);
g2.init ();
g2.build ();
printf ("%lld\n", g2.dp[1]);
}
return 0;
}
Conclusion
注意建虚树时： 1、不能使用
memset (h, 0, sizeof h);
来初始化图，因为时间复杂度是错的。
2、\(DP\) 的时候最好在建树的时候 \(DP\)， 否则可能挂。
转载于:https://www.cnblogs.com/ChiTongZ/p/11378123.html
相关资源：JAVA上百实例源码以及开源项目
