\u7ed9\u5b9a\u4e00\u68f5 n \u4e2a\u70b9\u7684\u70b9\u6743\u6811\uff0c\u540c\u65f6\u7ed3\u70b9\u5206\u4e3a\u9ed1\u70b9\u548c\u767d\u70b9\u4e24\u7c7b\u3002
\n\u8981\u6c42\u627e\u5230\u4e00\u6761\u957f\u5ea6\u6700\u5927\u7684\u8def\u5f84\uff0c\u4f7f\u5f97\u8def\u5f84\u4e0a\u7ecf\u8fc7\u7684\u9ed1\u70b9\u6570\u4e0d\u8d85\u8fc7 k \u4e2a\u3002<\/p>\n
<\/p>\n
\u70b9\u5206\u6cbb + \u52a8\u6001\u89c4\u5212\uff09
\n\u3002\u3002\u3002\u6709\u5f85\u5206\u6790\u3002<\/p>\n
\r\nconst int MOD = 1000000007;\r\nconst int INF = 0x7fffffff;\r\nconst int N = 200000 + 9, M = N * 2;\r\n\r\nint a[M], b[M], w[M], prd[M], suc[M]; \/\/ edge ..\r\nint dist[N], max_dep[N], dep[N], sz[N], hd[N]; bool isBlack[N]; \/\/ vertx ..\r\nint L[N], Ln, F[N], Fn, G[N], Gn; \/\/ core ..\r\nint n, n_, m, k, _c, c, ans;\r\n\r\ninline void remove(int x){\r\n if (x == hd[a[x]]) prd[hd[a[x]] = suc[x]] = 0;\r\n else suc[prd[suc[x]] = prd[x]] = suc[x];\r\n}\r\n\r\n#define v b[i]\r\ninline void dfs1(int u, int p){\r\n \r\n max_dep[u] = dep[u];\r\n \r\n if (!p){\r\n for(int i=hd[u];i;i=suc[i]){\r\n remove(i^1), dist[v] = dist[u] + w[i], dep[v] = dep[u] + isBlack[v];\r\n dfs1(v, u), checkMax(max_dep[u], max_dep[v]), L[Ln++] = v;\r\n }\r\n }\r\n else {\r\n for(int i=hd[u];i;i=suc[i]) if (v != p){\r\n dist[v] = dist[u] + w[i], dep[v] = dep[u] + isBlack[v];\r\n dfs1(v, u), checkMax(max_dep[u], max_dep[v]);\r\n }\r\n }\r\n\r\n}\r\n\r\ninline void dfs2(int u, int p){\r\n \r\n if (dep[u] >= Gn) return;\r\n checkMax(G[dep[u]], dist[u]);\r\n \r\n for(int i=hd[u];i;i=suc[i]) if (v != p){\r\n dfs2(v, u);\r\n }\r\n}\r\n\r\ninline void find_center(int u, int p){\r\n \r\n int blc = 0; sz[u] = 1;\r\n \r\n for(int i=hd[u];i;i=suc[i]) if (v != p){\r\n find_center(v, u), sz[u] += sz[v];\r\n checkMax(blc, sz[v]);\r\n }\r\n \r\n checkMax(blc, n_ - sz[u]);\r\n if (blc <= _c) _c = blc, c = u;\r\n}\r\n\r\ninline bool shller(int a, int b){\r\n return max_dep[a] < max_dep[b];\r\n}\r\n\r\ninline void stat(bool rt){\r\n \r\n if (!rt || k){\r\n \r\n sort(L, L+Ln, shller); Fn = 1; REP(i, Ln){\r\n \r\n Gn = min(max_dep[L[i]] + 1, k + !rt), dfs2(L[i], 0);\r\n FOR(j, 1, Gn) checkMax(G[j], G[j-1]);\r\n \r\n FOR(j, 0, Fn) {\r\n int t = k - j - rt;\r\n checkMax(ans, F[j] + (t<Gn?G[t]:G[Gn-1]));\r\n }\r\n checkMax(Fn, Gn); REP(j, Fn) checkMax(F[j], G[j]);\r\n \r\n \/\/REP(i, Gn) G[i] = 0;\r\n fill(G, G+Gn, 0);\r\n }\r\n \r\n \/\/REP(i, Fn) F[i] = 0;\r\n fill(F, F+Fn, 0);\r\n }\r\n \r\n Ln = 0;\r\n}\r\n\r\ninline void solve(int u = 1){\r\n \r\n _c = INF, find_center(u, 0), u = c; \r\n dep[u] = dist[u] = 0, dfs1(u, 0), \r\n \r\n stat(isBlack[u]);\r\n \r\n for(int i=hd[u];i;i=suc[i]){\r\n n_ = sz[v], solve(v);\r\n }\r\n}\r\n\r\n\r\nint main(){\r\n\r\n \/\/freopen("in.txt", "r", stdin);\r\n \/\/freopen("out.txt", "w", stdout);\r\n \/\/ios::sync_with_stdio(false);\r\n \r\n RD(n, k, m); DO(m) isBlack[RD()] = true;\r\n \r\n for (int i=2;i<n<<1;++i){\r\n RD(a[i], b[i]); RD_S(w[i]), a[i|1] = b[i], b[i|1] = a[i], w[i|1] = w[i];\r\n prd[hd[a[i]]] = i, suc[i] = hd[a[i]], hd[a[i]] = i; ++i;\r\n prd[hd[a[i]]] = i, suc[i] = hd[a[i]], hd[a[i]] = i;\r\n }\r\n \r\n n_ = n, solve(), printf("%d\\n", ans);\r\n}\r\n<\/pre>\nExternal link: <\/h3>\n