首页 > 代码库 > 1103 POI2007 大都市meg
1103 POI2007 大都市meg
树链剖分水过,单点修改,树状数组即可。
#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>#define N 250100using namespace std;int n, m, nowplace = 0;int p[N] = {0}, next[N], v[N], bnum = 0;int son[N] = {0}, fa[N], w[N], top[N], deep[N] = {0}, num[N];int t[N] = {0};int lowbit(int x) { return x & -x; }void dfs_1(int now, int fat){ int k = p[now]; num[now] = 1; int maxson = 0; fa[now] = fat; deep[now] = deep[fat] + 1; while (k) { dfs_1(v[k], now); if (num[v[k]] > maxson) { maxson = num[v[k]]; son[now] = v[k]; } num[now] += num[v[k]]; k = next[k]; }}void dfs_2(int now, int nowtop){ int k = p[now]; w[now] = ++nowplace; top[now] = nowtop; if (son[now]) dfs_2(son[now], nowtop); while (k) { if (v[k] != son[now]) dfs_2(v[k], v[k]); k = next[k]; }}void add(int now, int addnum){ while (now <= n) { t[now] += addnum; now += lowbit(now); } return;}int task(int now){ int ans = 0; while (now) { ans += t[now]; now -= lowbit(now); } return ans;}int ask(int u, int v){ int f1 = top[u], f2 = top[v]; if (deep[f1] < deep[f2]) { swap(f1, f2); swap(u, v); } if (f1 == f2) return task(max(w[u], w[v])) - task(min(w[u], w[v])-1); else { int ans = 0; ans = task(w[u]) - task(w[f1]-1); // 搞清先后 ans += ask(fa[f1], v); return ans; }}int main(){ scanf("%d", &n); for (int i = 1; i < n; ++i) { int x, y; scanf("%d%d", &x, &y); if (x > y) swap(x, y); bnum++; next[bnum] = p[x]; p[x] = bnum; v[bnum] = y; } dfs_1(1, 0); dfs_2(1, 1); for (int i = 2; i <= n; ++i) add(w[i], 1); scanf("%d", &m); m = m+n-1; for (int i = 1; i <= m; ++i) { char s[2]; scanf("%s", s); if (s[0] == ‘A‘) { int x, y; scanf("%d%d", &x, &y); if (x > y) swap(x, y); add(w[y], -1); } else { int x; scanf("%d", &x); printf("%d\n", ask(1, x)); } } return 0;}
1103 POI2007 大都市meg
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。