学会了用priority_queue实现带删除操作的堆.
/* I will wait for you*/ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define make make_pair #define fi first #define se second using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair pii; const int maxn = 200010; const int maxm = 1010; const int maxs = 26; const int inf = 0x3f3f3f3f; const int P = 1000000007; const double error = 1e-9; inline int read() { int x = 0, f = 1; char ch = getchar(); while (ch <= 47 || ch >= 58) f = (ch == 45 ? -1 : 1), ch = getchar(); while (ch >= 48 && ch <= 57) x = x * 10 + ch - 48, ch = getchar(); return x * f; } struct edge { int v, next; } e[maxn]; struct heap { priority_queue A, B; void push(int c) { A.push(c); } void erase(int c) { B.push(c); } void pop() { while (B.size() && A.top() == B.top()) A.pop(), B.pop(); A.pop(); } int size() { return A.size() - B.size(); } int first() { while (B.size() && A.top() == B.top()) A.pop(), B.pop(); return A.size() ? A.top() : 0; } int second() { if (size() <2) return 0; int x, y; x = first(), pop(); y = first(), push(x); return y; } } A, B[maxn >> 1], C[maxn >> 1]; int n, m, root, cnt, dfn, sum, tot, bin[maxn], lg[maxn], size[maxn], deep[maxn], sm[maxn], head[maxn], fa[maxn], st[maxn][20], pos[maxn], del[maxn], col[maxn]; void insert(int u, int v) { e[cnt] = (edge) {v, head[u]}, head[u] = cnt++; e[cnt] = (edge) {u, head[v]}, head[v] = cnt++; } void dfs(int u, int p) { st[++dfn][0] = deep[u], pos[u] = dfn; for (int i = head[u]; i != -1; i = e[i].next) { int v = e[i].v; if (v != p) { deep[v] = deep[u] + 1, dfs(v, u); st[++dfn][0] = deep[u]; } } } void find(int u, int p) { size[u] = 1, sm[u] = 0; for (int i = head[u]; i != -1; i = e[i].next) { int v = e[i].v; if (v != p && !del[v]) { find(v, u), size[u] += size[v]; sm[u] = max(sm[u], size[v]); } } sm[u] = max(sm[u], sum - size[u]); if (sm[u] v) swap(u, v); int t = lg[v - u + 1]; return min(st[u][t], st[v - bin[t] + 1][t]); } int dis(int u, int v) { return deep[u] + deep[v] - 2 * lca(u, v); } void turn_off(int u, int p) { if (u == p) { B[u].push(0); if (B[u].size() == 2) A.push(B[u].first()); } if (!fa[p]) return; int f = fa[p], d = dis(u, f), tmp = C[p].first(); C[p].push(d); if (d > tmp) { int mx = B[f].first() + B[f].second(), size = B[f].size(); B[f].push(d); if (tmp) B[f].erase(tmp); int now = B[f].first() + B[f].second(); if (now > mx) { if (size >= 2) A.erase(mx); if (B[f].size() >= 2) A.push(now); } } turn_off(u, f); } void turn_on(int u, int p) { if (u == p) { if (B[u].size() == 2) A.erase(B[u].first()); B[u].erase(0); } if (!fa[p]) return; int f = fa[p], d = dis(u, f), tmp = C[p].first(); C[p].erase(d); if (d == tmp) { int mx = B[f].first() + B[f].second(), size = B[f].size(); B[f].erase(d); if (C[p].first()) B[f].push(C[p].first()); int now = B[f].first() + B[f].second(); if (now = 2) A.erase(mx); if (B[f].size() >= 2) A.push(now); } } turn_on(u, f); } void init() { bin[0] = 1; for (int i = 1; i <= 20; i++) bin[i] = bin[i - 1] <<1; lg[0] = -1; for (int i = 1; i <= 200000; i++) lg[i] = lg[i >> 1] + 1; } int main() { n = read(), init(); memset(head, -1, sizeof head); for (int i = 1; i
京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有 