DFS序常见用法及代码实现

dfs序就是一棵树在dfs遍历时组成的节点序列.

它有这样一个特点:一棵子树的dfs序是一个区间. 下面是dfs序的基本代码:

void dfs(int x,int pre,int d){//L,R表示一个子树的范围
    L[x]=++tot;
    dep[x]=d;
    for(int i=0;i<e[x].size();i++){
        int y=e[x][i];
        if(y==pre)continue;
        dfs(y,x,d+1);
    }
    R[x]=tot;
}

给定一颗树, 和每个节点的权值.下面有7个经典的关于dfs序的问题:

下面所有问题都采用如图的树作为样例

都有以下初始化建树代码：

const int n = 15;
const int maxn = 1010;
struct E{
    int to,next;
}edge[maxn];
int head[maxn], cnt;
int t[maxn];
inline void addedge(int u,int v){
    edge[cnt] = (E){v,head[u]};
    head[u] = cnt++;
    edge[cnt] = (E){u,head[v]};
    head[v] = cnt++;
}
void build(){
    memset(head, -1, sizeof head);
    int tmp[28] = {1,2,1,3,2,4,2,5,2,6,3,7,3,8,5,9,5,10,7,11,7,12,12,13,12,14,12,15};
    for (int i = 0; i < 14*2; i+=2){
        addedge(tmp[i],tmp[i+1]);
    }
}

1.对某个节点X权值加上一个数W, 查询某个子树X里所有点权的和.

由于X的子树在DFS序中是连续的一段, 只需要维护一个dfs序列,用树状数组实现:单点修改和区间查询.

代码实现：

#include <bits/stdc++.h>

using namespace std;


const int n = 15;
const int maxn = 1010;
struct E{
    int to,next;
}edge[maxn];
int head[maxn], cnt;
int t[maxn];
inline void addedge(int u,int v){
    edge[cnt] = (E){v,head[u]};
    head[u] = cnt++;
    edge[cnt] = (E){u,head[v]};
    head[v] = cnt++;
}
void build(){
    memset(head, -1, sizeof head);
    int tmp[28] = {1,2,1,3,2,4,2,5,2,6,3,7,3,8,5,9,5,10,7,11,7,12,12,13,12,14,12,15};
    for (int i = 0; i < 14*2; i+=2){
        addedge(tmp[i],tmp[i+1]);
    }
}


int L[maxn], R[maxn], tot; //l[pos]表示子树的根(编号为pos的子树的dfs序号) R[pos]表示子树结尾的点 L[pos] ~ R[pos]表示以pos为根的子树 
void dfs(int u,int pre){
    L[u] = ++tot;
    for (int i = head[u]; ~i; i = edge[i].next){
        int v = edge[i].to;
        if (v == pre) continue;
        dfs(v,u);
    }
    R[u] = tot;
}


int tree[maxn];
int lowbit(int x){return x & -x;}
int add(int x,int w){
    while (x <= n){
        tree[x] += w;
        x += lowbit(x);
    }
}//对每个节点x加上w 
int sum(int x){
    int res = 0;
    while (x > 0){
        res += tree[x];
        x -= lowbit(x);
    }
    return res;
}
int query(int x){
    return sum(R[x]) - sum(L[x]-1);
}// 查询编号为x的子树里所有点的权值和 


int main(){
    build();
    dfs(1,-1);
    string op; // 输入Q x表示查询编号为x的子树里所有点权值和 Add x w表示在x节点加上w的权值 
    int x, w;
    while (cin >> op){
        if (op == "Q"){
            cin >> x;
            cout << query(x) << endl;
        } else {
            cin >> x >> w;
            add(L[x], w);
        }
    }
    return 0;
}
/*
input : 
Add 5 1
Add 6 1
Q 2
Add 7 2
Add 12 3
Add 13 1
Q 12
Q 3
Q 1
output : 
2
4
6
8
*/

 2. 对节点X到Y的最短路上所有点权都加一个数W, 查询某个点的权值.
这个操作等价于

a. 对X到根节点路径上所有点权加W
b. 对Y到根节点路径上所有点权加W
c. 对LCA(x, y)到根节点路径上所有点权值减W
d. 对LCA(x,y)的父节点 fa(LCA(x, y))到根节点路径上所有权值减W

于是要进行四次这样从一个点到根节点的区间修改.将问题进一步简化, 进行一个点X到根节点的区间修改, 查询其他一点Y时,只有X在Y的子树内, X对Y的值才有贡献且贡献值为W.当单点更新X时,X实现了对X到根的路径上所有点贡献了W.于是只需要更新四个点(单点更新) ,查询一个点的子树内所有点权的和(区间求和)即可.

#include <bits/stdc++.h>
using namespace std;
const int n = 15;
const int maxn = 1010;

const int lca_maxn = 1010;
const int tree_deep = 25;
int fa[lca_maxn][tree_deep];
int dep[lca_maxn], lg[lca_maxn];

void init_lg(){
    for(int i = 1; i <= n; ++i) //log_2(i)+1
    lg[i] = lg[i-1] + (1 << lg[i-1] == i);
}

struct E{
    int to,next;
}edge[maxn];
int head[maxn], cnt;
int t[maxn];
inline void addedge(int u,int v){
    edge[cnt] = (E){v,head[u]};
    head[u] = cnt++;
    edge[cnt] = (E){u,head[v]};
    head[v] = cnt++;
}
void build(){
    memset(head, -1, sizeof head);
    int tmp[28] = {1,2,1,3,2,4,2,5,2,6,3,7,3,8,5,9,5,10,7,11,7,12,12,13,12,14,12,15};
    for (int i = 0; i < 14*2; i+=2){
        addedge(tmp[i],tmp[i+1]);
    }
}


void dfs_lca(int u,int pre){
    fa[u][0] = pre, dep[u] = dep[pre] + 1;
    for (register int i = 1; i <= lg[dep[u]]; ++i){
        fa[u][i] = fa[fa[u][i-1]][i-1];
    }
    for (register int i = head[u]; ~i; i = edge[i].next){
        int v = edge[i].to; if (v != pre) dfs_lca(v,u);
    }
}
int lca(int x, int y){
    if (dep[x] < dep[y]) swap(x, y);
    while (dep[x] > dep[y]) x = fa[x][lg[dep[x] - dep[y]] - 1];
    if (x == y) return x;
    for (register int i = lg[dep[x] - 1]; i >= 0; --i){
        if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
    }
    return fa[x][0];
}

int L[maxn], R[maxn], tot, father[maxn];
int dfs(int u, int pre){
    father[u] = pre;
    L[u] = ++tot;
    for (int i = head[u]; ~i; i = edge[i].next) {
        int v = edge[i].to;
        if (v == pre) continue;
        dfs(v, u);
    }
    R[u] = tot;
}

int tree[maxn];
int lowbit(int x) { return x & -x;}
void update(int x, int val){
    while (x <= n) {
        tree[x] += val;
        x += lowbit(x);
    }
}
int sum (int x){
    int res = 0;
    while (x > 0) {
        res += tree[x];
        x -= lowbit(x);
    }
    return res;
}
int query (int x){
    return sum(R[x]) - sum(L[x]-1);
}

int add(int x,int y, int v){
    int LCA = lca(x, y);
    update(L[x], v);
    update(L[y], v);
    update(L[LCA], -v);
    if (father[LCA])
    update(L[father[LCA]], -v);
}

int main(){
    init_lg();
    build();
    dfs(1, 0);
    dfs_lca(1,0);
    string op;
    int x, y, w;
    while (cin >> op) {
        if (op == "Q") {// 输入Q x表示查询编号为x的点的权值 Add x y w表示在x节点到y节点的最短路上加上w的权值
            cin >> x;
            cout << query(x) << endl;
        } else {
            cin >> x >> y >> w;
            add(x, y, w);
        } 
    }
    return 0;
}
/*
input : 
Add 10 12 1
Add 3 9 2
Q 1
Q 11
Q 5
Q 9
Add 1 1 -1
Q 1
output : 
3
0
3
2
2
*/

 3.对节点X到Y的最短路上所有点权都加一个数W, 查询某个点子树的权值之和
同问题2中的修改方法, 转化为修改某点到根节点的权值加/减W
当修改某个节点A, 查询另一节点B时
只有A在B的子树内, Y的值会增加W×(depth[A]−depth[B]+1)==W×(depth[A]+1)−W×depth[B]W×(depth[A]−depth[B]+1)==W×(depth[A]+1)−W×depth[B]
同样是用树状数组来查询Y的子树, 修改 和 查询方法都要新增一个数组
第一个数组保存 W×(depth[A]+1)W×(depth[A]+1), 第二个数组保存 W
每次查询结果为Sum(ed[B])−Sum(st[B]−1)−(Sum1(ed[B])−Sum(st[B]−1))×depth[B]

#include <bits/stdc++.h>
using namespace std;
const int n = 15;
const int maxn = 1010;

const int lca_maxn = 1010;
const int tree_deep = 25;
int fa[lca_maxn][tree_deep];
int dep[lca_maxn], lg[lca_maxn];

void init_lg(){
    for(int i = 1; i <= n; ++i) //log_2(i)+1
    lg[i] = lg[i-1] + (1 << lg[i-1] == i);
}

struct E{
    int to,next;
}edge[maxn];
int head[maxn], cnt;
int t[maxn];
inline void addedge(int u,int v){
    edge[cnt] = (E){v,head[u]};
    head[u] = cnt++;
    edge[cnt] = (E){u,head[v]};
    head[v] = cnt++;
}
void build(){
    memset(head, -1, sizeof head);
    int tmp[28] = {1,2,1,3,2,4,2,5,2,6,3,7,3,8,5,9,5,10,7,11,7,12,12,13,12,14,12,15};
    for (int i = 0; i < 14*2; i+=2){
        addedge(tmp[i],tmp[i+1]);
    }
}


void dfs_lca(int u,int pre){
    fa[u][0] = pre, dep[u] = dep[pre] + 1;
    for (register int i = 1; i <= lg[dep[u]]; ++i){
        fa[u][i] = fa[fa[u][i-1]][i-1];
    }
    for (register int i = head[u]; ~i; i = edge[i].next){
        int v = edge[i].to; if (v != pre) dfs_lca(v,u);
    }
}
int lca(int x, int y){
    if (dep[x] < dep[y]) swap(x, y);
    while (dep[x] > dep[y]) x = fa[x][lg[dep[x] - dep[y]] - 1];
    if (x == y) return x;
    for (register int i = lg[dep[x] - 1]; i >= 0; --i){
        if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
    }
    return fa[x][0];
}

int L[maxn], R[maxn], tot, father[maxn];
int dfs(int u, int pre){
    father[u] = pre;
    L[u] = ++tot;
    for (int i = head[u]; ~i; i = edge[i].next) {
        int v = edge[i].to;
        if (v == pre) continue;
        dfs(v, u);
    }
    R[u] = tot;
}

int tree1[maxn];
int lowbit(int x) { return x & -x;}
void update1(int x, int val){
    while (x <= n) {
        tree1[x] += val;
        x += lowbit(x);
    }
}
int sum1 (int x){
    int res = 0;
    while (x > 0) {
        res += tree1[x];
        x -= lowbit(x);
    }
    return res;
}

int tree2[maxn];
void update2(int x,int val) {
    while (x <= n) {
        tree2[x] += val;
        x += lowbit(x);
    }
}
int sum2 (int x){
    int res = 0;
    while (x > 0){
        res += tree2[x];
        x -= lowbit(x);
    }
    return res;
}
int add(int x,int y, int v){
    int LCA = lca(x, y);
    update1(L[x], v);
    update2(L[x], (v*(dep[x]+1)));
    update1(L[y], v);
    update2(L[y], (v*(dep[y]+1)));
    update1(L[LCA], -v);
    update2(L[LCA], (-v*(dep[LCA]+1)));
    if (father[LCA])
    update1(L[father[LCA]], -v),update2(L[father[LCA]],(-v*(dep[father[LCA]]+1)));
}

int query(int x){
    return sum2(R[x]) - sum2(L[x]-1) - dep[x] * (sum1(R[x]) - sum1(L[x]-1));
}

int main(){
    init_lg();
    build();
    dfs(1, 0);
    dfs_lca(1,0);
    string op;
    int x, y, w;
    while (cin >> op) {
        if (op == "Q") {// 输入Q x表示查询编号为x的子树里所有点权值和 Add x y w表示在x节点到y节点的最短路上加上w的权值
            cin >> x;
            cout << query(x) << endl;
        } else {
            cin >> x >> y >> w;
            add(x, y, w);
        } 
    }
    return 0;
}
/*
input : 
Add 9 11 1
Q 2
Q 1
Q 7
Add 3 15 2
Q 3
output : 
3
7
2
11
*/

4.单点更新，树链和查询

树链和查询与树链修改类似，树链和(x,y)等于下面四个部分和相加：

1）.x到根节点的链上所有节点权值加。

2）.y到根节点的链上所有节点权值加。

3）.lca（x,y）到根节点的链上所有节点权值和的-1倍。

4）.fa(lca(x,y))到根节点的链上所有节点权值和的-1倍。

所以问题转化为：查询点x到根节点的链上的所有节点权值和。

修改节点x权值，当且仅当y是x的子孙节点时，x对y的值有贡献。

差分前缀和，y的权值等于dfs中[1,l[y]]的区间和。

单点修改：add(l[x],v),add(r[x]+1,-v);

#include <bits/stdc++.h>
using namespace std;
const int n = 15;
const int maxn = 1010;

const int lca_maxn = 1010;
const int tree_deep = 25;
int fa[lca_maxn][tree_deep];
int dep[lca_maxn], lg[lca_maxn];

void init_lg(){
    for(int i = 1; i <= n; ++i) //log_2(i)+1
    lg[i] = lg[i-1] + (1 << lg[i-1] == i);
}

struct E{
    int to,next;
}edge[maxn];
int head[maxn], cnt;
int t[maxn];
inline void addedge(int u,int v){
    edge[cnt] = (E){v,head[u]};
    head[u] = cnt++;
    edge[cnt] = (E){u,head[v]};
    head[v] = cnt++;
}
void build(){
    memset(head, -1, sizeof head);
    int tmp[28] = {1,2,1,3,2,4,2,5,2,6,3,7,3,8,5,9,5,10,7,11,7,12,12,13,12,14,12,15};
    for (int i = 0; i < 14*2; i+=2){
        addedge(tmp[i],tmp[i+1]);
    }
}


void dfs_lca(int u,int pre){
    fa[u][0] = pre, dep[u] = dep[pre] + 1;
    for (register int i = 1; i <= lg[dep[u]]; ++i){
        fa[u][i] = fa[fa[u][i-1]][i-1];
    }
    for (register int i = head[u]; ~i; i = edge[i].next){
        int v = edge[i].to; if (v != pre) dfs_lca(v,u);
    }
}
int lca(int x, int y){
    if (dep[x] < dep[y]) swap(x, y);
    while (dep[x] > dep[y]) x = fa[x][lg[dep[x] - dep[y]] - 1];
    if (x == y) return x;
    for (register int i = lg[dep[x] - 1]; i >= 0; --i){
        if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
    }
    return fa[x][0];
}

int L[maxn], R[maxn], tot, father[maxn];
int dfs(int u, int pre){
    father[u] = pre;
    L[u] = ++tot;
    for (int i = head[u]; ~i; i = edge[i].next) {
        int v = edge[i].to;
        if (v == pre) continue;
        dfs(v, u);
    }
    R[u] = tot;
}

int tree[maxn];
int lowbit(int x) { return x & -x;}
void update(int x, int val){
    while (x <= n) {
        tree[x] += val;
        x += lowbit(x);
    }
}
int sum (int x){
    int res = 0;
    while (x > 0) {
        res += tree[x];
        x -= lowbit(x);
    }
    return res;
}
int query (int x,int y){
    int LCA = lca(x, y);
    return sum(L[x]) + sum(L[y]) - sum(L[LCA]) - sum(L[father[LCA]]);
}

int add(int x, int v){
    update(L[x], v);
    update(R[x] + 1, -v);
}

int main(){
    init_lg();
    build();
    dfs(1, 0);
    dfs_lca(1,0);
    string op;
    int x, y, w;
    while (cin >> op) {
        if (op == "Q") {// 输入Q x y表示查询编号为x和y的点的所在链权值和 Add x w表示在x节点上加上w的权值
            cin >> x >> y;
            cout << query(x, y) << endl;
        } else {
            cin >> x >> w;
            add(x, w);
        } 
    }
    return 0;
}
/*
input : 
Add 5 2
Q 9 2
Q 2 5
Add 2 1
Add 1 3
Add 12 10
Q 15 3
Q 10 3
output :
2
2
10
6 
*/

5.子树修改，单点查询

修改节点x的子树权值，在dfs序上就是区间修改，单点权值查询就是单点查询。

区间修改，单点查询问题：树状数组或线段树即可;

#include <bits/stdc++.h>

using namespace std;


const int n = 15;
const int maxn = 1010;
struct E{
    int to,next;
}edge[maxn];
int head[maxn], cnt;
int t[maxn];
inline void addedge(int u,int v){
    edge[cnt] = (E){v,head[u]};
    head[u] = cnt++;
    edge[cnt] = (E){u,head[v]};
    head[v] = cnt++;
}
void build(){
    memset(head, -1, sizeof head);
    int tmp[28] = {1,2,1,3,2,4,2,5,2,6,3,7,3,8,5,9,5,10,7,11,7,12,12,13,12,14,12,15};
    for (int i = 0; i < 14*2; i+=2){
        addedge(tmp[i],tmp[i+1]);
    }
}


int L[maxn], R[maxn], tot; //l[pos]表示子树的根(编号为pos的子树的dfs序号) R[pos]表示子树结尾的点 L[pos] ~ R[pos]表示以pos为根的子树 
void dfs(int u,int pre){
    L[u] = ++tot;
    for (int i = head[u]; ~i; i = edge[i].next){
        int v = edge[i].to;
        if (v == pre) continue;
        dfs(v,u);
    }
    R[u] = tot;
}


int tree[maxn];
int lowbit(int x){return x & -x;}
int add(int x,int w){
    while (x <= n){
        tree[x] += w;
        x += lowbit(x);
    }
}//对每个节点x加上w 
int sum(int x){
    int res = 0;
    while (x > 0){
        res += tree[x];
        x -= lowbit(x);
    }
    return res;
}

void update (int x,int val) {
    add(L[x], val);
    add(R[x]+1, -val);
}

int main(){
    build();
    dfs(1,-1);
    string op; // 输入Q x表示查询编号为x的权值 Add x w表示在编号为x的子树里加上w的权值 
    int x, w;
    while (cin >> op){
        if (op == "Q"){
            cin >> x;
            cout << sum(L[x]) << endl;
        } else {
            cin >> x >> w;
            update(x, w);
        }
    }
    return 0;
}
/*
input : 
Add 2 1
Add 3 2
Q 5
Q 10
Q 8
Q 12
Q 15
Add 1 100
Q 4
Q 11 
output : 
1
1
2
2
2
101
102
*/

6.子树修改，子树和查询

题目等价与区间修改，区间查询问题。用树状数组或线段树即可。

#include <bits/stdc++.h>

using namespace std;


const int n = 15;
const int maxn = 1010;
struct E{
    int to,next;
}edge[maxn];
int head[maxn], cnt;
int t[maxn];
inline void addedge(int u,int v){
    edge[cnt] = (E){v,head[u]};
    head[u] = cnt++;
    edge[cnt] = (E){u,head[v]};
    head[v] = cnt++;
}
void build(){
    memset(head, -1, sizeof head);
    int tmp[28] = {1,2,1,3,2,4,2,5,2,6,3,7,3,8,5,9,5,10,7,11,7,12,12,13,12,14,12,15};
    for (int i = 0; i < 14*2; i+=2){
        addedge(tmp[i],tmp[i+1]);
    }
}


int L[maxn], R[maxn], tot; //l[pos]表示子树的根(编号为pos的子树的dfs序号) R[pos]表示子树结尾的点 L[pos] ~ R[pos]表示以pos为根的子树 
void dfs(int u,int pre){
    L[u] = ++tot;
    for (int i = head[u]; ~i; i = edge[i].next){
        int v = edge[i].to;
        if (v == pre) continue;
        dfs(v,u);
    }
    R[u] = tot;
}

int sum1[maxn], sum2[maxn];
void add(int p, int x){
    for(int i = p; i <= n; i += i & -i)
        sum1[i] += x, sum2[i] += x * p;
}
void range_add(int l, int r, int x){
    add(l, x), add(r + 1, -x);
}
int ask(int p){
    int res = 0;
    for(int i = p; i; i -= i & -i)
        res += (p + 1) * sum1[i] - sum2[i];
    return res;
}
int range_ask(int l, int r){
    return ask(r) - ask(l - 1);
}

int main(){
    build();
    dfs(1,-1);
    string op; // 输入Q x表示查询编号为x的权值 Add x w表示在编号为x的子树里加上w的权值 
    int x, w;
    while (cin >> op){
        if (op == "Q"){
            cin >> x;
            cout << range_ask(L[x], R[x]) << endl;
        } else {
            cin >> x >> w;
            range_add(L[x], R[x], w);
        }
    }
    return 0;
}
/*
input : 
Add 2 1
Q 1
Add 3 1
Q 1
Q 5
Add 10 100
Q 5
output : 
6
14
3
103
*/

 7. 对节点X的子树所有节点加上一个值W, 查询X到Y的路径上所有点的权值和
同问题4把路径上求和转化为四个点到根节点的和
X到根节点的和 + Y到根节点的和 - LCA(x, y)到根节点的和 - parent(LCA(x,y)) 到根节点的
再用刷漆只更新子树.
修改一点A, 查询某点B到根节点时, 只有B在A的子树内, A对B才有贡献.
贡献为W * (dep[B] - dep[A] + 1) => W * (1 - dep[A]) + W * dep[B]
和第三题一样, 用两个sum1,sum2维护 W *(dep[A] + 1),和W.
最后答案就是sum2*dep[B]-sum1.

#include <bits/stdc++.h>
using namespace std;
const int n = 15;
const int maxn = 1010;

const int lca_maxn = 1010;
const int tree_deep = 25;
int fa[lca_maxn][tree_deep];
int dep[lca_maxn], lg[lca_maxn];

void init_lg(){
    for(int i = 1; i <= n; ++i) //log_2(i)+1
    lg[i] = lg[i-1] + (1 << lg[i-1] == i);
}

struct E{
    int to,next;
}edge[maxn];
int head[maxn], cnt;
int t[maxn];
inline void addedge(int u,int v){
    edge[cnt] = (E){v,head[u]};
    head[u] = cnt++;
    edge[cnt] = (E){u,head[v]};
    head[v] = cnt++;
}
void build(){
    memset(head, -1, sizeof head);
    int tmp[28] = {1,2,1,3,2,4,2,5,2,6,3,7,3,8,5,9,5,10,7,11,7,12,12,13,12,14,12,15};
    for (int i = 0; i < 14*2; i+=2){
        addedge(tmp[i],tmp[i+1]);
    }
}


void dfs_lca(int u,int pre){
    fa[u][0] = pre, dep[u] = dep[pre] + 1;
    for (register int i = 1; i <= lg[dep[u]]; ++i){
        fa[u][i] = fa[fa[u][i-1]][i-1];
    }
    for (register int i = head[u]; ~i; i = edge[i].next){
        int v = edge[i].to; if (v != pre) dfs_lca(v,u);
    }
}
int lca(int x, int y){
    if (dep[x] < dep[y]) swap(x, y);
    while (dep[x] > dep[y]) x = fa[x][lg[dep[x] - dep[y]] - 1];
    if (x == y) return x;
    for (register int i = lg[dep[x] - 1]; i >= 0; --i){
        if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
    }
    return fa[x][0];
}

int L[maxn], R[maxn], tot, father[maxn];
int dfs(int u, int pre){
    father[u] = pre;
    L[u] = ++tot;
    for (int i = head[u]; ~i; i = edge[i].next) {
        int v = edge[i].to;
        if (v == pre) continue;
        dfs(v, u);
    }
    R[u] = tot;
}

int tree1[maxn];
int lowbit(int x) { return x & -x;}
void update1(int x, int val){
    while (x <= n) {
        tree1[x] += val;
        x += lowbit(x);
    }
}
int sum1 (int x){
    int res = 0;
    while (x > 0) {
        res += tree1[x];
        x -= lowbit(x);
    }
    return res;
}

int tree2[maxn];
void update2(int x,int val) {
    while (x <= n) {
        tree2[x] += val;
        x += lowbit(x);
    }
}
int sum2 (int x){
    int res = 0;
    while (x > 0){
        res += tree2[x];
        x -= lowbit(x);
    }
    return res;
}
int add(int x, int v){
    update1(L[x], v);
    update2(L[x], (v*(1-dep[x])));
    update1(R[x]+1, -v);
    update2(R[x]+1, (-v*(1-dep[x])));
}

int Q(int x) {
    return sum2(L[x]) + sum1(L[x]) * dep[x];
}

int query(int x, int y){
    int LCA = lca(x, y);
    return Q(x) + Q(y) - Q(LCA) - Q(father[LCA]);
}

int main(){
    init_lg();
    build();
    dfs(1, 0);
    dfs_lca(1,0);
    string op;
    int x, y, w;
    while (cin >> op) {
        if (op == "Q") {// 输入Q x y表示查询树链x到y的权值和 add x w表示在x的子树内所有点权值加上w 
            cin >> x >> y;
            cout << query(x, y) << endl;
        } else {
            cin >> x >> w;
            add(x, w);
        } 
    }
    return 0;
}
/*
input : 
Add 2 1
Q 6 9
Add 1 1
Q 1 15
Q 3 9
Q 2 2
Add 3 2
Q 3 11
output : 
4
5
8
2
9
*/