Description：
这是一道模板题。
给一棵有根树，这棵树由编号为 1…N 的 N 个结点组成。根结点的编号为 R。每个结点都有一个权值，结点 i 的权值为 vi。 接下来有 M 组操作，操作分为两类：
1 a x，表示将结点 a 的权值增加 x； 2 a，表示求结点 a 的子树上所有结点的权值之和。
Input
第一行有三个整数 N,M 和 R。 第二行有 N 个整数，第 i 个整数表示 vi。 在接下来的 N−1 行中，每行两个整数，表示一条边。 在接下来的 M 行中，每行一组操作。
Output
对于每组 2 a 操作，输出一个整数，表示「以结点 a 为根的子树」上所有结点的权值之和。
Example
样例输入 1
10 14 9 12 -6 -4 -3 12 8 9 6 6 2 8 2 2 10 8 6 2 7 7 1 6 3 10 9 2 4 10 5 1 4 -1 2 2 1 7 -1 2 10 1 10 5 2 1 1 7 -5 2 5 1 1 8 2 7 1 8 8 2 2 1 5 5 2 6
样例输出 1
21 34 12 12 23 31 4
D
F
S
DFS
DFS 序，它的主要思路就是将树形结构转化成线性结构，用
d
f
s
dfs
dfs 遍历一遍这棵树，进入到
x
x
x 节点有一个
i
n
in
in 时间戳，递归退出时有一个
o
u
t
out
out 时间戳，
x
x
x 节点的两个时间戳之间遍历到的点，就是根为
x
x
x 的子树的所有节点，他们的
d
f
s
dfs
dfs 进入时间戳是递增的。同时两个时间戳构成了一个区间，
x
x
x 节点在这段区间的最左端，这个区间就是一棵根节点为
x
x
x 的子树，对于区间的操作就是其他维护方式的应用了。
AC代码：
const int N
= 1e6 + 50;
int n
, q
, m
, r
, tot
, cnt
;
ll val
[N
], in
[N
], out
[N
], head
[N
], x
, num
[N
], sum
[N
];
struct node
{
int to
, next
;
} edge
[2 * N
];
void add(int u
, int v
)
{
edge
[tot
].to
= v
;
edge
[tot
].next
= head
[u
];
head
[u
] = tot
++;
}
void dfs(int u
, int fa
)
{
num
[++cnt
] = u
;
in
[u
] = cnt
;
for (int i
= head
[u
]; i
!= -1; i
= edge
[i
].next
)
{
int v
= edge
[i
].to
;
if (v
!= fa
)
dfs(v
, u
);
}
out
[u
] = cnt
;
}
void update(int x
, int y
)
{
while (x
<= n
)
{
sum
[x
] += y
;
x
+= lowbit(x
);
}
}
ll
ask(int x
)
{
ll res
= 0;
while (x
)
{
res
+= sum
[x
];
x
-= lowbit(x
);
}
return res
;
}
int main()
{
int u
, v
;
cnt
= 0;
sddd(n
, m
, r
);
rep(i
, 1, n
)
{
sld(val
[i
]);
head
[i
] = -1;
}
rep(i
, 1, n
- 1)
{
sdd(u
, v
);
add(u
, v
);
add(v
, u
);
}
dfs(r
, -1);
rep(i
, 1, n
)
update(in
[i
], val
[i
]);
rep(i
, 1, m
)
{
int op
, a
, x
;
sd(op
);
if (op
== 1)
{
sdd(a
, x
);
update(in
[a
], x
);
}
else
{
sd(a
);
pld(ask(out
[a
]) - ask(in
[a
] - 1));
}
}
return 0;
}
