Talk is Cheap, Show Me the Code!

0%

路径更新

Posted on In

给出一棵 n 个结点的树，有m个操作，每次把一条路径上每条边都加上1，最后按照每条边的输入顺序，输出每个条被增加的次数。

输入描述:

第一行两个整数n和m
接下来n-1行，每行两个整数，表示一条边
接下来m行，每行两个整数a和b，表示把a到b的路径上每条边都加1。
n, m<=10^5

输出描述:

按照边输入的顺序，输出每条边被增加的次数。

示例1
输入

5 3
1 2
1 3
3 4
3 5
1 4
1 5
2 3

输出

1
3
1
1

lujinggengxin.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include <vector>
using namespace std;

const int N = 300010;
const int S = 20;

int n, m;
int path[N];
int ans[N], ID[N]; //map node id to edge id

struct Node{
    int to, id;
};
vector<Node>edges[N];

int dis[N], dep[N];
int fa[N][S+2];
int cnt[N];
void dfs(int x, int f, int d){
    fa[x][0] = f, dep[x] = dep[f] +1, dis[x] = d;
    for(int i=0;i<edges[x].size();i++){
        int y = edges[x][i].to;
        if(y==f) continue;
        ID[y] = edges[x][i].id;  // ID maps y to edge id;
        dfs(y, x, d + 1);
    }
}

void goUp(int &x, int step){
//  starts from 0
    for(int i=0;i<=S;i++){
        if(step & (1<<i)) x = fa[x][i];
    }
}

int lca(int x, int y){
    if(dep[x] < dep[y]) swap(x, y);
    goUp(x, dep[x]-dep[y]);
    if(x==y) return x; // easy to forget
    for(int i=S;i>=0;i--){
        if(fa[x][i] != fa[y][i])
            x = fa[x][i], y= fa[y][i];
    }
    return fa[x][0];
}

void DFS(int x, int f){
    for(int i=0;i<edges[x].size();i++){
        int y = edges[x][i].to;
        if(y==f) continue;
        DFS(y, x);
        cnt[x] += cnt[y];
    }
    // crucial
    ans[ID[x]] = cnt[x];
}

int main(){
    scanf("%d%d", &n, &m);
    int a, b;
    for(int i=1;i<n;i++){
        scanf("%d%d", &a, &b);
        edges[a].push_back({b, i});
        edges[b].push_back({a, i});
    }
    dfs(1, 0, 0);
    for(int j=1;j<=S;j++)
        for(int i=1;i<=n;i++)
            fa[i][j] = fa[ fa[i][j-1] ][j-1];


    for(int i=1;i<=m;i++){
        scanf("%d%d", &a, &b);
        int c = lca(a, b);
        cnt[a]++, cnt[b]++, cnt[c]-=2;
    }

    DFS(1, 0);
    for(int i=1;i<n;i++) printf("%d\n", ans[i]);
    return 0;

}