# 某島

… : "…アッカリ～ン . .. . " .. .
July 30, 2012

## SPOJ 1825. Free tour II

### Analysis:

。。。有待分析。

const int MOD = 1000000007;
const int INF = 0x7fffffff;
const int N = 200000 + 9, M = N * 2;

int a[M], b[M], w[M], prd[M], suc[M]; // edge ..
int dist[N], max_dep[N], dep[N], sz[N], hd[N]; bool isBlack[N]; // vertx ..
int L[N], Ln, F[N], Fn, G[N], Gn; // core ..
int n, n_, m, k, _c, c, ans;

inline void remove(int x){
if (x == hd[a[x]]) prd[hd[a[x]] = suc[x]] = 0;
else suc[prd[suc[x]] = prd[x]] = suc[x];
}

#define v b[i]
inline void dfs1(int u, int p){

max_dep[u] = dep[u];

if (!p){
for(int i=hd[u];i;i=suc[i]){
remove(i^1), dist[v] = dist[u] + w[i], dep[v] = dep[u] + isBlack[v];
dfs1(v, u), checkMax(max_dep[u], max_dep[v]), L[Ln++] = v;
}
}
else {
for(int i=hd[u];i;i=suc[i]) if (v != p){
dist[v] = dist[u] + w[i], dep[v] = dep[u] + isBlack[v];
dfs1(v, u), checkMax(max_dep[u], max_dep[v]);
}
}

}

inline void dfs2(int u, int p){

if (dep[u] >= Gn) return;
checkMax(G[dep[u]], dist[u]);

for(int i=hd[u];i;i=suc[i]) if (v != p){
dfs2(v, u);
}
}

inline void find_center(int u, int p){

int blc = 0; sz[u] = 1;

for(int i=hd[u];i;i=suc[i]) if (v != p){
find_center(v, u), sz[u] += sz[v];
checkMax(blc, sz[v]);
}

checkMax(blc, n_ - sz[u]);
if (blc <= _c) _c = blc, c = u;
}

inline bool shller(int a, int b){
return max_dep[a] < max_dep[b];
}

inline void stat(bool rt){

if (!rt || k){

sort(L, L+Ln, shller); Fn = 1; REP(i, Ln){

Gn = min(max_dep[L[i]] + 1, k + !rt), dfs2(L[i], 0);
FOR(j, 1, Gn) checkMax(G[j], G[j-1]);

FOR(j, 0, Fn) {
int t = k - j - rt;
checkMax(ans, F[j] + (t<Gn?G[t]:G[Gn-1]));
}
checkMax(Fn, Gn); REP(j, Fn) checkMax(F[j], G[j]);

//REP(i, Gn) G[i] = 0;
fill(G, G+Gn, 0);
}

//REP(i, Fn) F[i] = 0;
fill(F, F+Fn, 0);
}

Ln = 0;
}

inline void solve(int u = 1){

_c = INF, find_center(u, 0), u = c;
dep[u] = dist[u] = 0, dfs1(u, 0),

stat(isBlack[u]);

for(int i=hd[u];i;i=suc[i]){
n_ = sz[v], solve(v);
}
}

int main(){

//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
//ios::sync_with_stdio(false);

RD(n, k, m); DO(m) isBlack[RD()] = true;

for (int i=2;i<n<<1;++i){
RD(a[i], b[i]); RD_S(w[i]), a[i|1] = b[i], b[i|1] = a[i], w[i|1] = w[i];
prd[hd[a[i]]] = i, suc[i] = hd[a[i]], hd[a[i]] = i; ++i;
prd[hd[a[i]]] = i, suc[i] = hd[a[i]], hd[a[i]] = i;
}

n_ = n, solve(), printf("%d\n", ans);
}