WC2018 即時戰略

AFO以後第一次更新（炮姐好萌啊QAQ史上最萌電容器）

題目鏈接在這裡：Universal Online Judge

神奇的wys出了一道神奇的題目

題目大意

給你一棵樹，一開始你只知道結點1。每次你可以知道這個已知點的一個兒子結點。請操作不超過若干次使整個樹變為已知。

做法一

很容易想到的一個做法是不斷詢問重心，由於探索到一個新結點以後會有加點的操作，因此需要用紫荊花之戀里的做法，也就是動態點分治，但是……寫起來有點煩啊……

做法二

神奇的 @g1n0st 告訴我做法一就相當於Link-Cut Tree的一個access操作，感覺有理有據，非常巧妙。每次探索一個結點，然從已知點走到這個點，邊走邊探索就行了，具體的走法就是在splay上二分，需要記錄一下每條鏈底端的結點。dataType=3需要特判一下，一開始天真地以為鏈就是(1,2)(2,3)...結果一發WA……鏈上的做法就是從兩邊靠近。因為提供的庫函數都是int型的，LCT就不寫指針了……

吐槽

哪位大佬能告訴我我的代碼還有什麼可改進的地方……UOJ的Extra Test#3過不掉啊/(ㄒoㄒ)/~~

#include "rts.h"#define N 300100typedef int tree[2];int fa[N], L_Bottom[N], R_Bottom[N];tree lct[N];bool vis[N];inline bool dir(int x) { return lct[fa[x]][1] == x; }inline bool isroot(int x) { return lct[fa[x]][0] != x && lct[fa[x]][1] != x; }inline void maintain(int x){ L_Bottom[x] = R_Bottom[x] = x; if (lct[x][0]) L_Bottom[x] = L_Bottom[lct[x][0]]; if (lct[x][1]) R_Bottom[x] = R_Bottom[lct[x][1]];}inline void rotate(int x){ int y = fa[x], z = fa[y], d = dir(x); if (!isroot(y)) lct[z][lct[z][1] == y] = x; lct[y][d] = lct[x][d ^ 1]; fa[lct[y][d]] = y; lct[x][d ^ 1] = y; fa[y] = x; fa[x] = z; maintain(y), maintain(x);}inline void splay(int x){ for (int y; (y = fa[x]) && !isroot(x); rotate(x)) if (!isroot(y)) rotate(dir(x) != dir(y) ? x : y);}inline void access(int x){ for (int t = 0; x; t = x, x = fa[x]) splay(x), lct[x][1] = t, maintain(x);}void play(int n, int T, int dataType){ vis[1] = 1; if (dataType == 3) { int l = 1, r = 1; for (int i = 2; i <= n; ++i) { if (!vis[i]) { int z = explore(l, i); if (!vis[z]) { vis[z] = 1; l = z; for (; l != i { z = explore(l, i); vis[z] = 1; l = z; } } else for (; r != i { z = explore(r, i); vis[z] = 1; r = z; } } } } else { for (int i = 2; i <= n; ++i) L_Bottom[i] = R_Bottom[i] = i; for (int i = 2; i <= n; ++i) if (!vis[i]) { int x = 1; for (;;) { splay(x); for (;;) { int z = explore(x, i); if (z == R_Bottom[lct[x][0]]) x = lct[x][0]; else if (z == L_Bottom[lct[x][1]]) x = lct[x][1]; else { if (!vis[z]) vis[z] = 1, fa[z] = x; else splay(z); x = z; break; } } if (x == i) break; } access(x); } }}

推薦閱讀：