http://poj.org/problem?id=3321
http://acm.hdu.edu.cn/showproblem.php?pid=3887
POJ 3321：
题意：给出一棵根节点为1的边不一定的树，然后给出问题：询问区间和 或者 节点值更新。
HDU 3887：
题意：和POJ 3321的题意差不多，只不过对每个节点询问不包含该节点的区间和
思路：今天才学了下才知道有DFS序这种东西，加上树状数组处理一下区间和 和 节点更新。
DFS序大概就是我们在DFS遍历一棵树的时候，在进入这个节点的时候，我们用一个变量记录此时的时间（代码中用cnt表示，也是可以看做是目前已经遍历过的节点的数目），然后分别用一个数组表示开始搜索这个节点的时间，和离开这个节点的时间（代码中用st代表开始，用ed代表结束）。然后我们可以发现在这段时间里面遍历过的节点都是该节点的儿子，即例如HDU3887这组样例：
15 7
7 10
7 1
7 9
7 3
7 4
10 14
14 2
14 13
9 11
9 6
6 5
6 8
3 15
3 12
0 0
我们的遍历顺序是这样的：7 1 1 3 15 15 12 12 3 4 4 10 14 2 2 13 13 14 10 9 11 11 6 5 5 8 8 6 9 7（手打的。。）
分别对应的下标是这样的：例如根节点7，它管辖的范围从前到后全部是，说明它就是根节点了。那么它的范围是【1,30】。
int cnt = ;
void dfs(int u, int fa)
{
que[++cnt] = u;
for(int k = head[u]; ~k; k = edge[k].nxt){
int v = edge[k].v;
if( v == fa ) continue;
dfs(v, u);
}
que[++cnt] = u;
}
dfs(, -);
我这里用的是前向星存的图，然后从根节点7开始遍历。
我先用一个数组来装遍历过的点的顺序，即que数组为我上面列出来的那个序列。
然后我们就按下面这样处理
for(int i = ; i <= cnt; i++) {
if( st[que[i]] == ) st[que[i]] = i;
else se[que[i]] = i;
}
把开始的位置和结束的位置分别装在st数组和ed数组中。
然后我们就可以根据这些条件建立起树状数组了。
询问的区间和为Query( ed[node] ) - Query( st[node] - 1 ) / 2（因为我们重复计数了，每个节点枚举了两次） ，更新就是Update( ed[node], value ); Update( st[node], value );
下面给出HDU 3887 的代码。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
#define N 100010 int st[N], se[N], ans[N], cnt;
int bit[*N],que[*N];
int head[N], tot;
struct node
{
int v, nxt;
}edge[N*];
//vector <int> edge[N];
//dfs序 + 树状数组
void addedge(int u, int v)
{
edge[tot].v = v;
edge[tot].nxt = head[u];
head[u] = tot++;
} void dfs(int u, int fa)
{
que[++cnt] = u;
for(int k = head[u]; ~k; k = edge[k].nxt){
int v = edge[k].v;
if( v == fa ) continue;
dfs(v, u);
}
que[++cnt] = u;
} int lowbit(int x)
{
return x & (-x);
} void Update(int x, int value)
{
while( x <= cnt ) {
bit[x] += value;
x += lowbit(x);
}
} int Query(int x)
{
int ans = ;
while( x > ) {
ans += bit[x];
x -= lowbit(x);
}
return ans;
} int main()
{
int n,p;
while(scanf("%d%d", &n, &p), n + p) { memset(head, -, sizeof(head));
tot = ; memset(bit,,sizeof(bit));
memset(st,,sizeof(st));
// for(int i = 1; i <= n; i++)
// edge[i].clear();
for(int i = ; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
addedge(u, v);
addedge(v, u);
// edge[u].push_back(v);
// edge[v].push_back(u);
}
cnt = ;
dfs(p, p); for(int i = ; i <= cnt; i++) {
if( st[que[i]] == ) st[que[i]] = i;
else se[que[i]] = i;
} for(int i = ; i <= cnt; i++) {
// printf("%d ", que[i]);
Update(i, );
}
putchar('\n');
//因为题意中要求子树中的节点不能比根节点的数大，因此从后往前枚举，
//然后删除掉枚举过的节点，这样就能保证后面的枚举中子树的点的数不会比根节点的大了
//而且题目的询问是不包含该询问的节点的，因此是(Query(se[i] - 1) - Query(st[i])) / 2
//而不是( Query(se[i]) - (Query[st[i]] - 1) ) / 2
for(int i = n; i > ; i--) {
ans[i] = (Query(se[i] - ) - Query(st[i])) / ;
Update(se[i], -);
Update(st[i], -);
} for(int i = ; i <= n; i++) {
printf("%d", ans[i]);
if( i == n ) printf("\n");
else printf(" ");
}
}
return ;
}
我根据上题的代码也写了一份POJ 3321的代码，顺利AC了之后，看了看别人的代码，发现自己处理的有点复杂 （就是MDZZ）。
先上一份看了别人之后修改过的DFS的代码
void dfs(int u, int fa)
{
st[u] = ++cnt;
for(int k = head[u]; ~k; k = edge[k].nxt){
int v = edge[k].v;
if( v != fa ) dfs(v, u);
}
ed[u] = cnt;
}
其实完全可以抛弃上一题的que数组，直接用这样的方式来处理st和ed数组。
虽然我觉得用que数组的话真的很好理解，但是变得比较冗杂了。
我们还是举HDU 3887的例子（谁让POJ 3321这个样例太不好举例了。。）
我们这样处理的话就是直接去掉我上面的重复的数字，变成：
node：7 1 3 15 12 4 10 14 2 13 9 11 6 5 8
st和ed两个数组对应的下标分别是：
st： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
ed：15 2 5 4 5 6 10 10 9 10 15 12 15 14 15 （对不齐，将就看看吧= =）
我们直接根据这样就可以建立一个树状数组了。
例如节点7的领域：【1,15】，
节点1的领域：【2,2】，
以此类推。
然后因为我们的树状数组变了，所以我们的询问和更新也肯定变了。
询问还是 【 st[node] - 1 ，ed[node] 】，只不过区间的值变小了，因为没有重复，我们不用对答案除以2了。
更新的区间就只要更新st[node]了，因为看上面，st[node]代表的是当下标取node时对应于该节点的左端点，所以只要更新st[node]就可以了。
还有这题可能卡了vector，我用的是前向星，一开始用vector超时了。
下面给出代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 100005
struct node
{
int v, nxt;
}edge[N*];
int bit[N], st[N], ed[N], head[N], mark[N], cnt, tot, n; void add(int u,int v)
{
edge[tot].v = v;
edge[tot].nxt = head[u];
head[u] = tot++;
edge[tot].v = u;
edge[tot].nxt = head[v];
head[v] = tot++;
} int lowbit(int x)
{
return x & (-x);
} int Query(int x)
{
int ans = ;
while( x > ){
ans += bit[x];
x -= lowbit(x);
}
return ans;
} void Update(int x, int value)
{
while( x <= n ){
bit[x] += value;
x += lowbit(x);
}
} void dfs(int u, int fa)
{
st[u] = ++cnt;
for(int k = head[u]; ~k; k = edge[k].nxt){
int v = edge[k].v;
if( v != fa ) dfs(v, u);
}
ed[u] = cnt;
} int main()
{
tot = , cnt = ;
memset(bit, , sizeof(bit));
memset(head, -, sizeof(head));
scanf("%d", &n);
for(int i = ; i < n; i++){
int u, v;
scanf("%d%d", &u, &v);
add(u, v);
}
for(int i = ; i <= n; i++){
Update(i, );
mark[i] = ;
} dfs(, -); int q;
scanf("%d", &q);
while(q--){
char s[];
int node;
scanf("%s%d", s, &node);
if(s[] == 'Q'){
int ans = Query(ed[node]) - Query(st[node] - );
printf("%d\n", ans);
}
else{
mark[node] *= -;
Update(st[node], mark[node]);
}
printf("%d %d\n", bit[st[]], bit[ed[]]);
}
return ;
}
//15
//1 10
//1 7
//1 9
//1 3
//1 4
//10 14
//14 2
//14 13
//9 11
//9 6
//6 5
//6 8
//3 15
//3 12
//8
//Q 1
//C 1
//C 3
//C 5
//Q 1
//C 1
//Q 1
//Q 5