# 某島

… : "…アッカリ～ン . .. . " .. .
March 14, 2020

# 解題報告

—— 官方題解

## 虛仙人掌

### 虛樹

```const int N = int(3e5) + 9, LV = 21;

VII adj[N]; int dfn[N], lfn[N], dep[N]; LL depp[N];
int tt;

int n,m,cnt,ind,top;
int fa[N][LV];

bool cmp(int a,int b) {
return dfn[a]<dfn[b];
}
void dfs(int u) {
dfn[u] = ++tt;
int v = it.fi, w = it.se; if (v == fa[u][0]) continue;
fa[v][0] = u; for (int lv=0;fa[v][lv+1]=fa[fa[v][lv]][lv];++lv);
dep[v] = dep[u] + 1;
depp[v] = depp[u] + w;
dfs(v);
}
lfn[u] = tt;
}
inline int move_up(int x, int t){
for (int lv=0;t;++lv,t>>=1)
if (t&1) x = fa[x][lv];
return x;
}
inline int move_to(int x, int t){
return move_up(x, dep[x]-t);
}
inline int lca(int x, int y) {
if (dep[x]>dep[y]) swap(x,y); y=move_to(y, dep[x]); if (x==y) return x;
DWN(lv, LV, 0) if (fa[x][lv]!=fa[y][lv]) x = fa[x][lv], y = fa[y][lv];
return fa[x][0];
}
inline int dist(int x, int y) {
return dep[x] + dep[y] - 2*dep[lca(x,y)];
}

namespace Virtual_Tree {
LL f[N], diameter;

void dfs(int u) {
f[u] = 0; for (auto v: adj[u]) {
dfs(v); LL w = depp[v] - depp[u]; f[v] += w;
checkMax(diameter, f[u] + f[v]);
checkMax(f[u], f[v]);
}
checkMax(diameter, f[u]);
}

void gao() {
VI T; Rush {
int x; RD(x);
T.PB(x);
}
UNQ(T, cmp); DWN(i, SZ(T)-1, 0) {
int z = lca(T[i], T[i+1]);
T.PB(z);
}
UNQ(T, cmp); top = 0; for (auto u: T) {
while (top && lfn[sta[top]] < dfn[u]) --top;
if (top) adj[sta[top]].PB(u); sta[++top] = u;
}

diameter = -INFF; dfs(T[0]);
printf("%lld\n", diameter);
}
}

int main() {

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif

RD(n, m); DO(m) {
int x, y, w; RD(x, y, w);
}
dfs(1); Rush Virtual_Tree::gao();
}
```

### 虛仙人掌

```    void add_edge(int x, int y) {
if (x > G.n && x != C.fa[0][y]) { // 如果是從方點連出去，並且 y 不是連出去的那個孩子。
int z = C.move_up(y, C.dep[y]-C.dep[x]-1);
x = z;
}
}
```

```
const int N = int(6e5) + 9, LV = 21;
int sta[N], top;

struct Raw_Graph {
map<int, int> adj[N]; int dfn[N], low[N], tt; LL D[N];
int n;

void add_edge(int x, int y, int w) {
} else {
}
}

void init() {
RD(n); Rush {
int x, y, w; RD(x, y, w);
}
}
void tarjan(int = 1, int = -1);
} G;

struct Cactus_Tree {
vector<pair<int, LL> > adj[N]; int dfn[N], lfn[N], tt, dep[N]; LL D[N], L[N];
int fa[LV][N];
int n;

void add_edge(int x, int y, LL w) {
}

inline int move_up(int x, int t){
for (int lv=0;t;++lv,t>>=1)
if (t&1) x = fa[lv][x];
return x;
}
inline int lca(int x, int y) {
if (dep[x]>dep[y]) swap(x,y); y=move_up(y, dep[y]-dep[x]); if (x==y) return x;
DWN(lv, LV, 0) if (fa[lv][x]!=fa[lv][y]) x = fa[lv][x], y = fa[lv][y];
return fa[0][x];
}

void dfs(int u = 1) {
dfn[u] = ++tt;
int v = it->fi; LL w = it->se;
dep[v] = dep[u] + 1; D[v] = D[u] + w;
fa[0][v] = u; for (int lv=0;fa[lv+1][v]=fa[lv][fa[lv][v]];++lv);
dfs(v);
}
lfn[u] = tt;
}

void init() {
n = G.n; G.tt = 0; G.tarjan();
tt = 0; dfs();
}
} C;

void Raw_Graph::tarjan(int u, int p) {
low[u] = dfn[u] = ++tt;
sta[++top] = u;
int v = it->fi, w = it->se; if (v == p) continue;
if (!dfn[v]) {
D[v] = D[u] + w; tarjan(v, u);
checkMin(low[u], low[v]);
if (dfn[v] == low[v]) C.add_edge(u, v, w); // tree edge
} else if (dfn[v] < dfn[u]) { // find circle
checkMin(low[u], dfn[v]);
C.add_edge(v, ++C.n, 0); C.L[C.n] = D[u]-D[v]+w;
for (int i=top;sta[i]!=v;--i) {
LL d = D[sta[i]] - D[v];
}
}
}
--top;
}

bool cmp(int a, int b) {
return C.dfn[a] < C.dfn[b];
}

struct Virtual_Tree {

LL f[N], z;

void add_edge(int x, int y) {
if (x > G.n && x != C.fa[0][y]) {
int z = C.move_up(y, C.dep[y]-C.dep[x]-1);
x = z;
}
}

int q[2*N], cz, op; vector<pair<LL, LL> > c;

void dfs(int u) {
dfs(v); LL w = C.D[v] - C.D[u];
if (u <= G.n) checkMax(z, f[u] + f[v] + w);
checkMax(f[u], f[v] + w);
}
if (u > G.n) {
c.clear();
for (auto v: adj[u]) c.PB({f[v], G.D[v]});
for (auto v: adj[u]) c.PB({f[v], G.D[v] + C.L[u]});
cz = 0, op = 0; q[0] = 0; FOR(i, 1, SZ(c)) {
while (cz <= op && c[i].se - c[q[cz]].se > C.L[u]/2) ++cz;
if (cz <= op) checkMax(z, c[i].fi + c[q[cz]].fi + c[i].se - c[q[cz]].se);
while (cz <= op && c[q[op]].fi - c[q[op]].se <= c[i].fi - c[i].se) --op;
q[++op] = i;
}
}

for (auto v: adj[u]) f[v] = 0;
}

VI T;

void gao() {
Rush T.PB(RD());

UNQ(T, cmp); DWN(i, SZ(T)-1, 0) {
int z = C.lca(T[i], T[i+1]);
T.PB(z);
}
UNQ(T, cmp); top = 0; for (auto u: T) {
while (top && C.lfn[sta[top]] < C.dfn[u]) --top;
if (top) add_edge(sta[top], u); sta[++top] = u;
}
z = 0; dfs(T[0]); printf("%lld\n", z);
f[T[0]] = 0; T.clear();
}
} T;

int main() {

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif

G.init(); C.init();
Rush T.gao();
}

```