首页 > 代码库 > 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