[BZOJ 1095][ZJOI2007]Hide 捉迷藏
转载请注明出处:http://danihao123.is-programmer.com/
蛤蛤蛤我这题终于调出来了~(然后1A了)
点分树处女作。其实点分树的思想并不难理解,就是把点分的过程抽象化到一棵树上。
其实唯一比较烦人的就是点分树上的儿子给父亲的贡献要开一个堆处理……非常烦人。
代码(其中有海量本来拿来调试的代码,慎读):
/************************************************************** Problem: 1095 User: danihao123 Language: C++ Result: Accepted Time:15268 ms Memory:128944 kb ****************************************************************/ #include <cstdio> #include <cstring> #include <cstdlib> #include <cctype> #include <algorithm> #include <utility> #include <set> #include <vector> #include <queue> const int maxn = 100005; const int maxe = maxn << 1; int first[maxn]; int next[maxe], to[maxe]; void add_edge(int u, int v) { static int cnt = 0; cnt ++; next[cnt] = first[u]; first[u] = cnt; to[cnt] = v; } int size[maxn], hson[maxn], fa[maxn], dep[maxn]; void dfs_1(int x, int father = 0, int depth = 1) { size[x] = 1; fa[x] = father; dep[x] = depth; int max_siz = 0; for(int i = first[x]; i; i = next[i]) { int v = to[i]; if(v != father) { dfs_1(v, x, depth + 1); size[x] += size[v]; if(size[v] > max_siz) { max_siz = size[v]; hson[x] = v; } } } } int dfn[maxn], top[maxn], tid[maxn]; void dfs_2(int x, int father = 0, int a = 1) { static int dfn_clk = 0; dfn[x] = ++ dfn_clk; tid[dfn[x]] = x; top[x] = a; if(!hson[x]) { return; } else { dfs_2(hson[x], x, a); } for(int i = first[x]; i; i = next[i]) { int v = to[i]; if(v != father && v != hson[x]) { dfs_2(v, x, v); } } } int lca(int x, int y) { while(top[x] != top[y]) { if(dep[top[x]] < dep[top[y]]) std::swap(x, y); x = fa[top[x]]; } if(dep[x] > dep[y]) { return y; } else { return x; } } bool vis[maxn]; int siz[maxn]; void gen_siz(int x, int fa = 0) { siz[x] = 1; for(int i = first[x]; i; i = next[i]) { int v = to[i]; if(!vis[v] && v != fa) { gen_siz(v, x); siz[x] += siz[v]; } } } int nrt, rt; void gen_rt(int x, int fa = 0) { bool ok = (2 * siz[x] >= siz[nrt]); for(int i = first[x]; i; i = next[i]) { int v = to[i]; if(!vis[v] && v != fa) { ok = ok && (2 * siz[v] <= siz[nrt]); gen_rt(v, x); } } if(ok) rt = x; } int crt; int cfa[maxn]; typedef std::priority_queue<int> heap; struct dheap { heap Q, D; void push(int x) { Q.push(x); } void pop() { while(!D.empty() && Q.top() == D.top()) { #ifdef DEBUG printf("deleting %d\n", D.top()); #endif Q.pop(); D.pop(); } Q.pop(); } int top() { while(!D.empty() && Q.top() == D.top()) { #ifdef DEBUG printf("deleting %d\n", D.top()); #endif Q.pop(); D.pop(); } return Q.top(); } void del(int x) { D.push(x); } size_t size() { return Q.size() - D.size(); } int sec() { int fir = top(); pop(); int ret = top(); push(fir); return ret; } }; dheap all; dheap Q[maxn], sg[maxn]; int divide(int x) { nrt = rt = x; gen_siz(x); gen_rt(x); x = rt; vis[x] = true; for(int i = first[x]; i; i = next[i]) { int v = to[i]; if(!vis[v]) { cfa[divide(v)] = x; } } return x; } int n; int get_ans(dheap &q) { return q.top() + q.sec(); } bool sta[maxn]; int dist(int x, int y) { int ret = dep[x] + dep[y] - 2 * dep[lca(x, y)]; #ifdef DEBUG printf("dist(%d, %d) : %d\n", x, y, ret); #endif return ret; } void light_on(int p) { sta[p] = true; int x = p; int og = -1, ng = 0; while(x) { int old_ans = -1, old_sg = -1; if(Q[x].size() > 1) { old_ans = get_ans(Q[x]); } if(sg[x].size() > 0) { old_sg = sg[x].top(); } if(og != -1) Q[x].del(og); if(ng != -1) Q[x].push(ng); if(Q[x].size() > 1) all.push(get_ans(Q[x])); if(old_ans != -1) all.del(old_ans); if(cfa[x] != 0) { og = old_sg; sg[x].push(dist(p, cfa[x])); ng = sg[x].top(); } x = cfa[x]; } } void light_off(int p) { sta[p] = false; int x = p; int og = 0, ng = -1; while(x) { int old_ans = -1, old_sg = -1; if(Q[x].size() > 1) old_ans = get_ans(Q[x]); if(sg[x].size() > 0) { old_sg = sg[x].top(); } if(og != -1) Q[x].del(og); if(ng != -1) Q[x].push(ng); #ifdef DEBUG printf("%d deleting %d\n", x, og); #endif if(Q[x].size() > 1) all.push(get_ans(Q[x])); if(old_ans != -1) all.del(old_ans); #ifdef DEBUG int tmp = -1; if(Q[x].size() > 1) tmp = get_ans(Q[x]); printf("ans of %d : %d -> %d\n", x, old_ans, tmp); #endif if(cfa[x] != 0) { og = old_sg; sg[x].del(dist(p, cfa[x])); if(sg[x].size() > 0) { ng = sg[x].top(); } else { ng = -1; } } x = cfa[x]; } } void print_dheap(dheap &q) { std::vector<int> V; while(q.size() > 0) { int t = q.top(); q.pop(); printf("%d ", t); V.push_back(t); } puts(""); for(int i = 0; i < V.size(); i ++) { q.push(V[i]); } } int main() { scanf("%d", &n); for(int i = 1; i <= n - 1; i ++) { int u, v; scanf("%d%d", &u, &v); add_edge(u, v); add_edge(v, u); } dfs_1(1); dfs_2(1); #ifdef DEBUG for(int i = 1; i <= n; i ++) { printf("%d top fa hson : %d %d %d\n", i, top[i], fa[i], hson[i]); } #endif crt = divide(1); #ifdef DEBUG printf("crt id %d\n", crt); for(int i = 1; i <= n; i ++) { printf("cfa[%d] : %d\n", i, cfa[i]); } #endif int num = 0; for(int i = 1; i <= n; i ++) { light_on(i); num ++; #ifdef DEBUG printf("heap while inserting %d : ", i); print_dheap(all); #endif } int q; scanf("%d", &q); while(q --) { char op[3]; scanf("%s", op); if(op[0] == 'G') { if(num == 0) { puts("-1"); } else if(num == 1) { puts("0"); } else { printf("%d\n", all.top()); } } else { int i; scanf("%d", &i); if(sta[i]) { light_off(i); num --; } else { light_on(i); num ++; } } #ifdef DEBUG print_dheap(all); #endif } return 0; }