# BZOJ 2125: 最短路

## 題解

### 圓方樹

const int N = int(2e4) + 9, LV = 15;

int dfn[N], low[N], tt, sta[N], top;
int fa[LV][N], dep[N], D[N], DD[N], L[N];
int n, nn;

inline int move_up(int x, int t){
for (int lv=0;t;++lv,t&gt;&gt;=1)
if (t&amp;1) x = fa[lv][x];
return x;
}
inline int lca(int x, int y) {
if (dep[x]&gt;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 getLCA(int x, int y, int &amp;a, int &amp;b, int &amp;z) {
if (dep[x]&gt;dep[y]) swap(x,y); y=move_up(y, dep[y]-dep[x]); if (x==y) {z = x; return;}
DWN(lv, LV, 0) if (fa[lv][x]!=fa[lv][y]) x = fa[lv][x], y = fa[lv][y];
a = x; b = y; z = fa[0][x];
}

void add_edge(int u, int v, LL w) {
}

#define v it-&gt;fi
#define w it-&gt;se
void tarjan(int u = 1, int p = -1) {
low[u] = dfn[u] = ++tt;
sta[++top] = u;
ECH(it, adj[u]) if (v != p) {
if (!dfn[v]) {
D[v] = D[u] + w; tarjan(v, u);
checkMin(low[u], low[v]);
if (dfn[v] == low[v]) add_edge(u, v, w); // tree edge
} else if (dfn[v] &lt; dfn[u]) { // find circle
checkMin(low[u], dfn[v]);
add_edge(v, ++nn, 0); L[nn] = D[u]-D[v]+w;
for (int i=top;sta[i]!=v;--i) {
int d = D[sta[i]]-D[v];
}
}
}
--top;
}
#define p fa[0][u]
void dfs(int u = 1) {
dep[v] = dep[u] + 1; DD[v] = DD[u] + w;
fa[0][v] = u; for (int lv=0;fa[lv+1][v]=fa[lv][fa[lv][v]];++lv);
dfs(v);
}
}
#undef p
#undef w
#undef v

int main() {

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

int Q, m; RD(n, m, Q);

DO(m) {
int x, y, w; RD(x, y, w);
}

nn = n; tarjan(); dfs();

DO(Q) {
int x, y, a, b, z; RD(x, y); getLCA(x, y, a, b, z);

//cout &lt;&lt; x &lt;&lt; " " &lt;&lt; y &lt;&lt; " " &lt;&lt;  z&lt;&lt; endl;

if (z &lt;= n) { // round one ...
OT(DD[x]+DD[y]-DD[z]*2);
} else { // square one ...
int d = abs(D[a]-D[b]);
OT(DD[x]+DD[y]-DD[a]-DD[b]+min(d, L[z]-d));
}
}
}


### 動態仙人掌

https://www.luogu.com.cn/record/31868182

# 論自殺

。後來我還找兔子認真的討論了「自殺」這件事情。。。我當時只是覺得，如果真的要「自殺」的話，應該怎麼做都會成功吧。。最簡單的方法可能是，找個高樓大廈，忘記一切，跳下去就好。。。而且在都市圈的話，卧軌應該也是很多人的一個選擇。。不過兔子說，那樣會麻煩到其他人。。打掃起來很不方便，燒炭的話，如果失敗會變成植物人。。。（所以果然還是「靜脈注射氯化鋇」最好？。。。）。。

# 分類

– 主動型自殺，為達成個人因素以外的目的而進行的自殺。例如，自殺攻擊是為達到某種目的而自殺。（E.g. 三島由紀夫）
– 被動型自殺，僅個人因素導致的自殺。比如逃離性自殺，例如社會壓力而產生心理疾病、藥物、醉酒、物質濫用等，是外因導致其自殺。（E.g. 阿蘭圖靈）

– 安樂死：個體以藉助他人幫助的形式來完成自己的自殺。
– 謀殺自殺：一個人用謀殺的方式，讓另一個人或幾個人在他本人之前或同時死去。
– 相約自殺：兩個或兩個以上的個體之間立下協定，通常是因個人原因，同時或先後自殺。
– 集體自殺：集體自殺指一群人為了同一目的而自殺或互相殺害，而這通常與真實或意識到的迫害有關。（代表作，亂步奇譚）

## 主動型自殺

• 自殺式襲擊：犧牲自己以完成攻擊目的。如神風特攻隊、恐怖攻擊中的自殺炸彈客。
• 政治目的性自殺：為傳達某種理念而自殺，例如死諫、殉情或以死明志，例如在某重要地標自焚。此類自殺亦常見要求他人協助完成者。如2019年自殺的香港反對修訂逃犯條例示威者、鄭南榕。

## 被動型自殺

• 脅迫性自殺：為了控制他人（罪惡感、恐懼）而自殺。因認為自己遭到某人惡意待遇（因動機來自感受到他人惡意，故列為被動型），而以死的方式作為報復手段。某些地方文化認為人死後產生的鬼可代為復仇，亦屬這一類。
• 責任性自殺：為了顯示責任心而自殺，如早期日本在戰敗時的切腹自殺（因具備文化因素，亦含主動性成分）。在現代，此類自殺常見於強迫性格傾向者。（E.g. 如最近負責日本武漢撤僑的首相官邸官員）
• 逃離性自殺：為了躲避某種事物（如惡疾、痛苦、恐慌、空虛等感受），或是被某事逼迫（如被逼債、畏罪、政權垮台），因而自殺。（大部分情況）

# 方式

「還有什麼比創作出來的故事更真實的呢？」
—— 【剩餘榨值023】在巨大的 shock 後，我們所思考的、所做的一切都將與此有關 34:00

## 墜樓

### 夢日記

。。自殺自然是十分誘人的… 所有描繪自殺的作品裡。。最令人印象深刻的自然還是《夢日記》。在夢中辛苦遊歷收集了所有十二扇門的世界。最後的最後。。居然是選擇結束了自己的生命。。。留給玩家無限多的想像空間。。。

## 自刎

### 霸王別姬

「吾聞漢購我頭千金，邑萬戶，吾為若德。」
—— 《史記 項羽本紀》

—— 李清照《夏日絕句》

「漢兵已略地，四面楚歌聲。大王意氣盡，賤妾何聊生！」

「我們演一個劇，第一要自己懂得這個劇的意義，第二要明白觀眾對於這個戲的感情……還有人以為戲劇是用來開心取樂的，以為是玩意兒，其實不然」，「一個戲總有它的意義，算起總賬來，就是一切戲劇都有提高人類生活目標的意義」

TBD

TBD

## 沉江

「俺史可法亡國罪臣，那容的冠裳而去。」
「你看茫茫世界，留著俺史可法何處安放。累死英雄，到此日看江山換主，無可留戀。」

。。。

—— 小島 みなこ, [Jul 10, 2020 at 7:25:44 PM]

# 生死觀

「人死之後，葬在地下，佔得多少土地？」

「墳中安葬著丟番圖。上帝給予的童年佔六分之一，又過十二分之一，兩頰長胡，再過七分之一，點燃起結婚的蠟燭。五年之後天賜貴子，可憐遲到的寧馨兒，享年僅及其父之半，便進入冰冷的墓。悲傷只有用數論的研究去彌補，又過四年，他也走完了人生的旅途。」

（類似的還有最近的 「Flight recorder inventor: Do Not Open」

TBD