DFS序 参考许昊然《数据结构漫谈》

时间：2024-09-06 13:05:26

网上特别讲DFS序的东西好像很少

太简单了? 实用性不大?

看了论文中 7个经典问题, 觉得挺有用的

原文

"所谓DFS序, 就是DFS整棵树依次访问到的结点组成的序列"

"DFS序有一个很强的性质: 一颗子树的所有节点在DFS序内是连续的一段, 利用这个性质我们可以解决很多问题"

基本代码 :

void Dfs(int u, int fa, int dep)

{

    seq[++cnt] = u;

    st[u] = cnt;

    int len = edge[u].size();

    for(int i = ; i < len; i++) {

        int v = edge[u][i];

        if(v != fa) {

            Dfs(v, u, dep+);

        }

    }

    seq[++cnt] = u;

    ed[u] = cnt;

}

关于原文中列出的7个经典问题, 分别实现一下

给定一颗树, 和每个节点的权值

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

解 :

由于X子树在DFS序中是连续的一段, 只需要维护一个序列,

支持单点修改和区间查询, 用树状数组就能实现

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

using namespace std;

const int MAXN = 1e5+;

vector<int> edge[MAXN];

int s[*MAXN];

int seq[*MAXN];

int st[MAXN];

int ed[MAXN];

int cnt;

int Lowbit(int x)

{

    return x & (-x);

}

void Add(int x, int val, int n)

{

    for(int i = x; i <= n; i += Lowbit(i)) {

        s[i] += val;

    }

}

int Sum(int x)

{

    int res = ;

    for(int i = x; i > ; i -= Lowbit(i)) {

        res += s[i];

    }

    return res;

}

void Dfs(int u, int fa)

{

    seq[++cnt] = u;

    st[u] = cnt;

    int len = edge[u].size();

    for(int i = ; i < len; i++) {

        int v = edge[u][i];

        if(v != fa) {

            Dfs(v, u);

        }

    }

    seq[++cnt] = u;

    ed[u] = cnt;

}

void Init(int n)

{

    for(int i = ; i <= n; i++) {

        edge[i].clear();

    }

    memset(s, , sizeof(s));

}

int main()

{

    int n, op;

    int u, v, w;

    int cmd;

    while(scanf("%d %d", &n, &op) != EOF) {

        Init(n);

        for(int i = ; i < n-; i++) {

            scanf("%d %d", &u, &v);

            edge[u].push_back(v);

            edge[v].push_back(u);

        }

        cnt = ;

        Dfs(, -);

        while(op--) {

            scanf("%d", &cmd);

            if(cmd == ) {

                scanf("%d %d", &u, &w);

                Add(st[u], w, cnt);

            }

            else if(cmd == ) {

                scanf("%d", &u);

                printf("%d\n", Sum(ed[u]) - Sum(st[u] - ));

            }

        }

    }

    return ;

}

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

解 :

这个操作等价于

a. 对X到根节点路径上所有点权加W

b. 对Y到根节点路径上所有点权加W

c. 对LCA(x, y)到根节点路径上所有点权值减W

d. 对LCA(x,y)的父节点 parent(LCA(x, y))到根节点路径上所有权值减W

于是要进行四次这样从一个点到根节点的区间修改

将问题进一步简化, 进行一个点X到根节点的区间修改, 查询其他一点Y时

只有X在Y的子树内, X对Y的值才有贡献且贡献值为W

于是只需要更新四个点, 查询一个点的子树内所有点权的和即可

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

using namespace std;

const int MAXN = 1e5+;

vector<int> edge[MAXN];

int s[*MAXN];

int seq[*MAXN];

int seq1[*MAXN];

int depth[*MAXN];

int first[MAXN];

int dp[*MAXN][];

int st[MAXN];

int ed[MAXN];

int parent[MAXN];

int cnt, num;

int Lowbit(int x)

{

    return x & (-x);

}

void Add(int x, int val, int n)

{

    if(x <= ) return;

    for(int i = x; i <= n; i += Lowbit(i)) {

        s[i] += val;

    }

}

int Sum(int x)

{

    int res = ;

    for(int i = x; i > ; i -= Lowbit(i)) {

        res += s[i];

    }

    return res;

}

void Dfs(int u, int fa, int dep)

{

    parent[u] = fa;

    seq[++cnt] = u;

    seq1[++num] = u;

    first[u] = num;

    depth[num] = dep;

    st[u] = cnt;

    int len = edge[u].size();

    for(int i = ; i < len; i++) {

        int v = edge[u][i];

        if(v != fa) {

            Dfs(v, u, dep+);

            seq1[++num] = u;

            depth[num] = dep;

        }

    }

    seq[++cnt] = u;

    ed[u] = cnt;

}

void RMQ_Init(int n)

{

    for(int i = ; i <= n; i++) {

        dp[i][] = i;

    }

    for(int j = ; ( << j) <= n; j++) {

        for(int i = ; i + ( << j) -  <= n; i++) {

            int a = dp[i][j-], b = dp[i + ( << (j-))][j-];

            dp[i][j] = depth[a] < depth[b] ? a : b;

        }

    }

}

int RMQ_Query(int l, int r)

{

    int k = ;

    while(( << (k + )) <= r - l + ) k++;

    int a = dp[l][k], b = dp[r-(<<k)+][k];

    return depth[a] < depth[b] ? a : b;

}

int LCA(int u, int v)

{

    int a = first[u], b = first[v];

    if(a > b) a ^= b, b ^= a, a ^= b;

    int res = RMQ_Query(a, b);

    return seq1[res];

}

void Init(int n)

{

    for(int i = ; i <= n; i++) {

        edge[i].clear();

    }

    memset(s, , sizeof(s));

}

int main()

{

    int n, op;

    int u, v, w;

    int cmd;

    while(scanf("%d %d", &n, &op) != EOF) {

        Init(n);

        for(int i = ; i < n-; i++) {

            scanf("%d %d", &u, &v);

            edge[u].push_back(v);

            edge[v].push_back(u);

        }

        cnt = , num = ;

        Dfs(, -, );

        RMQ_Init(num);

        while(op--) {

            scanf("%d", &cmd);

            if(cmd == ) {

                scanf("%d %d %d", &u, &v, &w);

                int lca = LCA(u, v);

                Add(st[u], w, cnt);

                Add(st[v], w, cnt);

                Add(lca, -w, cnt);

                Add(parent[lca], -w, cnt);

            }

            else if(cmd == ) {

                scanf("%d", &u);

                printf("%d\n", Sum(ed[u]) - Sum(st[u] - ));

            }

        }

    }

    return ;

}

3. 对节点X到Y的最短路上所有点权都加一个数W, 查询某个点子树的权值之和

解 :

同问题2中的修改方法, 转化为修改某点到根节点的权值加/减W

当修改某个节点A, 查询另一节点B时

只有A在B的子树内, Y的值会增加 W * (depth[A] - depth[B] + 1) == W * (depth[A] + 1) - W * depth[B]

同样是用树状数组来查询Y的子树, 修改 和 查询方法都要新增一个数组

第一个数组保存 W * (depth[A] + 1), 第二个数组保存 W

每次查询结果为Sum(ed[B]) - Sum(st[B]-1) - (Sum1(ed[B]) - Sum(st[B]-1)) * depth[B]

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

using namespace std;

const int MAXN = 1e5+;

vector<int> edge[MAXN];

int s[*MAXN];

int s1[*MAXN];

int seq[*MAXN];

int seq1[*MAXN];

int depth[*MAXN];

int first[MAXN];

int dp[*MAXN][];

int st[MAXN];

int ed[MAXN];

int parent[MAXN];

int cnt, num;

int Lowbit(int x)

{

    return x & (-x);

}

void Add(int x, int val, int n)

{

    if(x <= ) return;

    for(int i = x; i <= n; i += Lowbit(i)) {

        s[i] += val;

    }

}

void Add1(int x, int val, int n)

{

    if(x <= ) return;

    for(int i = x; i <= n; i += Lowbit(i)) {

        s1[i] += val;

    }

}

int Sum(int x)

{

    int res = ;

    for(int i = x; i > ; i -= Lowbit(i)) {

        res += s[i];

    }

    return res;

}

int Sum1(int x)

{

    int res = ;

    for(int i = x; i > ; i -= Lowbit(i)) {

        res += s1[i];

    }

    return res;

}

void Dfs(int u, int fa, int dep)

{

    parent[u] = fa;

    seq[++cnt] = u;

    seq1[++num] = u;

    first[u] = num;

    depth[num] = dep;

    st[u] = cnt;

    int len = edge[u].size();

    for(int i = ; i < len; i++) {

        int v = edge[u][i];

        if(v != fa) {

            Dfs(v, u, dep+);

            seq1[++num] = u;

            depth[num] = dep;

        }

    }

    seq[++cnt] = u;

    ed[u] = cnt;

}

void RMQ_Init(int n)

{

    for(int i = ; i <= n; i++) {

        dp[i][] = i;

    }

    for(int j = ; ( << j) <= n; j++) {

        for(int i = ; i + ( << j) -  <= n; i++) {

            int a = dp[i][j-], b = dp[i + ( << (j-))][j-];

            dp[i][j] = depth[a] < depth[b] ? a : b;

        }

    }

}

int RMQ_Query(int l, int r)

{

    int k = ;

    while(( << (k + )) <= r - l + ) k++;

    int a = dp[l][k], b = dp[r-(<<k)+][k];

    return depth[a] < depth[b] ? a : b;

}

int LCA(int u, int v)

{

    int a = first[u], b = first[v];

    if(a > b) a ^= b, b ^= a, a ^= b;

    int res = RMQ_Query(a, b);

    return seq1[res];

}

void Init(int n)

{

    for(int i = ; i <= n; i++) {

        edge[i].clear();

    }

    memset(s, , sizeof(s));

}

int main()

{

    int n, op;

    int u, v, w;

    int cmd;

    while(scanf("%d %d", &n, &op) != EOF) {

        Init(n);

        for(int i = ; i < n-; i++) {

            scanf("%d %d", &u, &v);

            edge[u].push_back(v);

            edge[v].push_back(u);

        }

        cnt = , num = ;

        Dfs(, -, );

        RMQ_Init(num);

        while(op--) {

            scanf("%d", &cmd);

            if(cmd == ) {

                scanf("%d %d %d", &u, &v, &w);

                int lca = LCA(u, v);

                Add(st[u], w * depth[first[u]] + w, cnt);

                Add1(st[u], w, cnt);

                Add(st[v], w * depth[first[v]] + w, cnt);

                Add1(st[v], w, cnt);

                Add(lca, -(w * depth[first[lca]] + w), cnt);

                Add1(lca, -w, cnt);

                Add(parent[lca], -(w * depth[first[parent[lca]]] + w), cnt);

                Add1(parent[lca], -w, cnt);

            }

            else if(cmd == ) {

                scanf("%d", &u);

                printf("%d\n", Sum(ed[u]) - Sum(st[u] - ) - \

                               depth[first[u]] * (Sum1(ed[u]) - Sum1(st[u] - )));

            }

        }

    }

    return ;

}

4. 对某个点X权值加上一个数W, 查询X到Y路径上所有点权之和

解 :

求X到Y路径上所有的点权之和, 和前面X到Y路径上所有点权加一个数相似

这个问题转化为

X到根节点的和 + Y到根节点的和 - LCA(x, y)到根节点的和 - parent(LCA(x,y)) 到根节点的和

于是只要支持单点修改, 区间查询即可

要注意的是修改, 要在该点开始出现位置加W, 在结束位置减W

这样能保证在该节点子树内的能加到这个W, 不在该点子树内的无影响

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

using namespace std;

const int MAXN = 1e5+;

vector<int> edge[MAXN];

int s[*MAXN];

int s1[*MAXN];

int seq[*MAXN];

int seq1[*MAXN];

int depth[*MAXN];

int first[MAXN];

int dp[*MAXN][];

int st[MAXN];

int ed[MAXN];

int parent[MAXN];

int cnt, num;

int Lowbit(int x)

{

    return x & (-x);

}

void Add(int x, int val, int n)

{

    if(x <= ) return;

    for(int i = x; i <= n; i += Lowbit(i)) {

        s[i] += val;

    }

}

int Sum(int x)

{

    int res = ;

    for(int i = x; i > ; i -= Lowbit(i)) {

        res += s[i];

    }

    return res;

}

void Dfs(int u, int fa, int dep)

{

    parent[u] = fa;

    seq[++cnt] = u;

    seq1[++num] = u;

    first[u] = num;

    depth[num] = dep;

    st[u] = cnt;

    int len = edge[u].size();

    for(int i = ; i < len; i++) {

        int v = edge[u][i];

        if(v != fa) {

            Dfs(v, u, dep+);

            seq1[++num] = u;

            depth[num] = dep;

        }

    }

    seq[++cnt] = u;

    ed[u] = cnt;

}

void RMQ_Init(int n)

{

    for(int i = ; i <= n; i++) {

        dp[i][] = i;

    }

    for(int j = ; ( << j) <= n; j++) {

        for(int i = ; i + ( << j) -  <= n; i++) {

            int a = dp[i][j-], b = dp[i + ( << (j-))][j-];

            dp[i][j] = depth[a] < depth[b] ? a : b;

        }

    }

}

int RMQ_Query(int l, int r)

{

    int k = ;

    while(( << (k + )) <= r - l + ) k++;

    int a = dp[l][k], b = dp[r-(<<k)+][k];

    return depth[a] < depth[b] ? a : b;

}

int LCA(int u, int v)

{

    int a = first[u], b = first[v];

    if(a > b) a ^= b, b ^= a, a ^= b;

    int res = RMQ_Query(a, b);

    return seq1[res];

}

void Init(int n)

{

    for(int i = ; i <= n; i++) {

        edge[i].clear();

    }

    memset(s, , sizeof(s));

}

int main()

{

    int n, op;

    int u, v, w;

    int cmd;

    while(scanf("%d %d", &n, &op) != EOF) {

        Init(n);

        for(int i = ; i < n-; i++) {

            scanf("%d %d", &u, &v);

            edge[u].push_back(v);

            edge[v].push_back(u);

        }

        cnt = , num = ;

        Dfs(, -, );

        RMQ_Init(num);

        while(op--) {

            scanf("%d", &cmd);

            if(cmd == ) {

                scanf("%d %d", &u, &w);

                Add(st[u], w, cnt);

                Add(ed[u], -w, cnt);

            }

            else if(cmd == ) {

                scanf("%d %d", &u, &v);

                int lca = LCA(u, v);

                printf("%d\n", Sum(st[u]) + Sum(st[v]) - Sum(st[lca]) - Sum(st[parent[lca]]));

            }

        }

    }

    return ;

}

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

解 :

对DFS序来说, 子树内所有节点加W, 就是一段区间加W

所以这个问题就是 区间修改, 单点查询

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

using namespace std;

const int MAXN = 1e5+;

vector<int> edge[MAXN];

int s[*MAXN];

int s1[*MAXN];

int seq[*MAXN];

int seq1[*MAXN];

int depth[*MAXN];

int first[MAXN];

int dp[*MAXN][];

int st[MAXN];

int ed[MAXN];

int parent[MAXN];

int cnt, num;

int Lowbit(int x)

{

    return x & (-x);

}

void Add(int x, int val, int n)

{

    if(x <= ) return;

    for(int i = x; i <= n; i += Lowbit(i)) {

        s[i] += val;

    }

}

int Sum(int x)

{

    int res = ;

    for(int i = x; i > ; i -= Lowbit(i)) {

        res += s[i];

    }

    return res;

}

void Dfs(int u, int fa)

{

    seq[++cnt] = u;

    st[u] = cnt;

    int len = edge[u].size();

    for(int i = ; i < len; i++) {

        int v = edge[u][i];

        if(v != fa) {

            Dfs(v, u);

        }

    }

    seq[++cnt] = u;

    ed[u] = cnt;

}

void Init(int n)

{

    for(int i = ; i <= n; i++) {

        edge[i].clear();

    }

    memset(s, , sizeof(s));

}

int main()

{

    int n, op;

    int u, v, w;

    int cmd;

    while(scanf("%d %d", &n, &op) != EOF) {

        Init(n);

        for(int i = ; i < n-; i++) {

            scanf("%d %d", &u, &v);

            edge[u].push_back(v);

            edge[v].push_back(u);

        }

        cnt = ;

        Dfs(, -);

        while(op--) {

            scanf("%d", &cmd);

            if(cmd == ) {

                scanf("%d %d", &u, &w);

                Add(st[u], w, cnt);

                Add(ed[u], -w, cnt);

            }

            else if(cmd == ) {

                scanf("%d", &u);

                printf("%d\n", Sum(u));

            }

        }

    }

    return ;

}

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

解 :

子树所有节点加W, 就是某段区间加W, 查询某个子树的权值和, 就是查询某段区间的和

区间修改区间求和, 是线段树的经典问题, 用线段树可以很好解决

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

using namespace std;

typedef struct {

    int l, r, sum, add;

} Seg;

const int MAXN = 1e5+;

Seg T[*MAXN];

vector<int> edge[MAXN];

int s[*MAXN];

int seq[*MAXN];

int st[MAXN];

int ed[MAXN];

int cnt;

void Dfs(int u, int fa)

{

    seq[++cnt] = u;

    st[u] = cnt;

    int len = edge[u].size();

    for(int i = ; i < len; i++) {

        int v = edge[u][i];

        if(v != fa) {

            Dfs(v, u);

        }

    }

    seq[++cnt] = u;

    ed[u] = cnt;

}

void Build(int l, int r, int k)

{

    T[k].l = l, T[k].r = r, T[k].sum = T[k].add;

    if(l == r) return;

    int mid = (l + r) >> ;

    Build(l, mid, k<<);

    Build(mid+, r, k<<|);

}

void PushDown(int k)

{

    if(T[k].add) {

        T[k<<].sum += (T[k<<].r - T[k<<].l + ) * T[k].add;

        T[k<<].add += T[k].add;

        T[k<<|].sum += (T[k<<|].r - T[k<<|].l + ) * T[k].add;

        T[k<<|].add += T[k<<].add;

        T[k].add = ;

    }

}

void PushUp(int k)

{

    T[k].sum = T[k<<].sum + T[k<<|].sum;

}

void Update(int l, int r, int val, int k)

{

    if(T[k].l == l && T[k].r == r) {

        T[k].sum += (r - l + ) * val;

        T[k].add += val;

        return ;

    }

    PushDown(k);

    int mid = (T[k].l + T[k].r) >> ;

    if(r <= mid) Update(l, r, val, k<<);

    else if(l > mid) Update(l, r, val, k<<|);

    else {

        Update(l, mid, val, k<<);

        Update(mid+, r, val, k<<|);

    }

    PushUp(k);

}

int Query(int l, int r, int k)

{

    if(T[k].l == l && T[k].r == r) {

        return T[k].sum;

    }

    PushDown(k);

    int mid = (T[k].l + T[k].r) >> ;

    if(r <= mid) return Query(l, r, k<<);

    else if(l > mid) return Query(l, r, k<<|);

    else {

        return Query(l, mid, k<<) + Query(mid+, r, k<<|);

    }

}

void Init(int n)

{

    for(int i = ; i <= n; i++) {

        edge[i].clear();

    }

}

int main()

{

    int n, op;

    int u, v, w;

    int cmd;

    while(scanf("%d %d", &n, &op) != EOF) {

        Init(n);

        for(int i = ; i < n-; i++) {

            scanf("%d %d", &u, &v);

            edge[u].push_back(v);

            edge[v].push_back(u);

        }

        cnt = ;

        Dfs(, -);

        Build(, cnt, );

        while(op--) {

            scanf("%d", &cmd);

            if(cmd == ) {

                scanf("%d %d", &u, &w);

                Update(st[u], ed[u], w, );

            }

            else if(cmd == ) {

                scanf("%d", &u);

                printf("%d\n", Query(st[u], ed[u], ) / );

            }

        }

    }

    return ;

}

7. 对节点X的子树所有节点加上一个值W, 查询X到Y的路径上所有点的权值和

解:

同问题4把路径上求和转化为四个点到根节点的和

X到根节点的和 + Y到根节点的和 - LCA(x, y)到根节点的和 - parent(LCA(x,y)) 到根节点的和

修改一点A, 查询某点B到根节点时, 只有B在A的子树内, A对B才有贡献

贡献为W * (depth[B] - depth[A] + 1) == W * (1 - depth[A]) + W * depth[B]

和第三题一样, 用两个树状数组维护 W *(depth[A] + 1), W * depth[B]

同样要注意修改某点时, 在一点开始位置加, 在其结束位置减

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

using namespace std;

typedef struct {

    int l, r, sum, add;

} Seg;

const int MAXN = 1e5+;

Seg T[*MAXN];

vector<int> edge[MAXN];

int s[*MAXN];

int s1[*MAXN];

int seq[*MAXN];

int seq1[*MAXN];

int depth[*MAXN];

int first[MAXN];

int dp[*MAXN][];

int parent[MAXN];

int st[MAXN];

int ed[MAXN];

int cnt, cnt1;

int Lowbit(int x)

{

    return x & (-x);

}

void Add(int x, int val, int n)

{

    if(x <= ) return ;

    for(int i = x; i <= n; i += Lowbit(i)) {

        s[i] += val;

    }

}

void Add1(int x, int val, int n)

{

    if(x <= ) return ;

    for(int i = x; i <= n; i += Lowbit(i)) {

        s1[i] += val;

    }

}

int Sum(int x)

{

    int res = ;

    for(int i = x; i > ; i -= Lowbit(i)) {

        res += s[i];

    }

    return res;

}

int Sum1(int x)

{

    int res = ;

    for(int i = x; i > ; i -= Lowbit(i)) {

        res += s1[i];

    }

    return res;

}

void RMQ_Init(int n)

{

    for(int i = ; i <= n; i++) {

        dp[i][] = i;

    }

    for(int j = ; ( << j) <= n; j++) {

        for(int i = ; i + ( << j) -  <= n; i++) {

            int a = dp[i][j-], b = dp[i + ( << (j-))][j-];

            dp[i][j] = depth[a] < depth[b] ? a : b;

        }

    }

}

int RMQ_Query(int l, int r)

{

    int k = ;

    while(( << (k + )) <= r - l + ) k++;

    int a = dp[l][k], b = dp[r-( << k)+][k];

    return depth[a] < depth[b] ? a : b;

}

int LCA(int u, int v)

{

    int a = first[u], b = first[v];

    if(a > b) a ^= b, b ^= a, a ^= b;

    int res = RMQ_Query(a, b);

    return seq1[res];

}

void Dfs(int u, int fa, int dep)

{

    seq[++cnt] = u;

    seq1[++cnt1] = u;

    first[u] = cnt1;

    parent[u] = fa;

    depth[cnt1] = dep;

    st[u] = cnt;

    int len = edge[u].size();

    for(int i = ; i < len; i++) {

        int v = edge[u][i];

        if(v != fa) {

            Dfs(v, u, dep+);

            seq1[++cnt1] = u;

            depth[cnt1] = dep;

        }

    }

    seq[++cnt] = u;

    ed[u] = cnt;

}

void Init(int n)

{

    for(int i = ; i <= n; i++) {

        edge[i].clear();

    }

    memset(s, , sizeof(s));

    memset(s1, , sizeof(s1));

}

void Debug()

{

    int u, v;

    while() {

        scanf("%d %d", &u, &v);

        printf("The LCA of %d %d is %d\n", u, v, LCA(u, v));

    }

}

int main()

{

    int n, op;

    int u, v, w;

    int cmd;

    while(scanf("%d %d", &n, &op) != EOF) {

        Init(n);

        for(int i = ; i < n-; i++) {

            scanf("%d %d", &u, &v);

            edge[u].push_back(v);

            edge[v].push_back(u);

        }

        cnt = cnt1 = ;

        Dfs(, , );

        RMQ_Init(cnt1);

        while(op--) {

            scanf("%d", &cmd);

            if(cmd == ) {

                scanf("%d %d", &u, &w);

                Add(st[u], w * ( - depth[first[u]]), cnt);

                Add(ed[u], -w * ( - depth[first[u]]), cnt);

                Add1(st[u], w, cnt);

                Add1(ed[u], -w, cnt);

            }

            else if(cmd == ) {

                scanf("%d %d", &u, &v);

                int lca = LCA(u, v);

                int par = parent[lca];

                int ans = Sum(st[u]);

                ans += depth[first[u]] * Sum1(st[u]);

                ans += Sum(st[v]);

                ans += depth[first[v]] * Sum1(st[v]);

                ans -= Sum(st[lca]);

                ans -= depth[first[lca]] * Sum1(st[lca]);

                ans -= Sum(st[par]);

                ans -= depth[first[par]] * Sum1(st[par]);

                printf("%d\n", ans);

            }

        }

    }

    return ;

}

相关文章