1103 POI2007 大都市meg

树链剖分水过，单点修改，树状数组即可。

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#define N 250100

using namespace std;

int n, m, nowplace = ;

int p[N] = {}, next[N], v[N], bnum = ;

int son[N] = {}, fa[N], w[N], top[N], deep[N] = {}, num[N];

int t[N] = {};

int lowbit(int x) { return x & -x; }

void dfs_1(int now, int fat)

{

    int k = p[now]; num[now] = ; int maxson = ;

    fa[now] = fat; deep[now] = deep[fat] + ;

    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 = ;

    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])-);

    else

    {

        int ans = ;

        ans = task(w[u]) - task(w[f1]-); // 搞清先后

        ans += ask(fa[f1], v);

        return ans;

    }

}

int main()

{

    scanf("%d", &n);

    for (int i = ; 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(, ); dfs_2(, );

    for (int i = ; i <= n; ++i) add(w[i], );

    scanf("%d", &m); m = m+n-;

    for (int i = ; i <= m; ++i)

    {

        char s[]; scanf("%s", s);

        if (s[] == 'A')

        {

            int x, y; scanf("%d%d", &x, &y);

            if (x > y) swap(x, y);

            add(w[y], -);

        }

        else

        {

            int x; scanf("%d", &x);

            printf("%d\n", ask(, x));

        }

    }

    return ;

}

还有DFS序做法，其实就是求点到根的路径权值和，样例的DFS序 为 1 4 5 5 4 3 3 2 2 1

我们把入序的地方+1 出序的地方-1， 查询的时候求入序的前缀和 - 1 就OK了（因为要减去多出来的1节点）

修改的时候入序和出序都改为0

上代码：

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#define N 250010

using namespace std;

int n, m, nowplace = ;

int p[N] = {}, next[N], v[N], bnum = ;

int t[N*] = {};

int first[N], second[N];

int lowbit(int x) { return x & -x; }

void add(int now, int addnum)

{

    while (now <= *n)

    {

        t[now] += addnum;

        now += lowbit(now);

    }

}

void dfs(int now)

{

    int k = p[now]; add(++nowplace, );

    first[now] = nowplace;

    while (k)

    {

        dfs(v[k]);

        k = next[k];

    }

    add(++nowplace, -);

    second[now] = nowplace;

}

int ask(int now)

{

    int ans = ;

    while (now)

    {

        ans += t[now];

        now -= lowbit(now);

    }

    return ans;

}

int main()

{

    scanf("%d", &n);

    for (int i = ; 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();

    scanf("%d", &m); m = m+n-;

    for (int i = ; i <= m; ++i)

    {

        char s[]; scanf("%s", s);

        if (s[] == 'A')

        {

            int x, y; scanf("%d%d", &x, &y);

            if (x < y) swap(x, y);

            add(first[x], -);

            add(second[x], );

        }

        else

        {

            int x; scanf("%d", &x);

            printf("%d\n", ask(first[x])-);

        }

    }

    return ;

}