复赛二：天天爱跑步(running)

  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
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159

/**************************************************************** 
 * Description: 2016年提高组第二题  天天爱跑步
 * Author: Alex Li
 * Date: 2024-09-30 23:27:41
 * LastEditTime: 2024-10-01 10:44:15
****************************************************************/
#include<iostream>
#include<cmath>
using namespace std;

const int SIZE=300000; // 定义常量，假设节点数和玩家数不超过300000

int n, m, tot, h[SIZE], deep[SIZE], fa[SIZE][20], w[SIZE];

// 定义边的结构体，包含目标节点和下一条边的索引
struct edge{
    int to, next;
}E[SIZE*2], e1[SIZE*2], e2[SIZE*2];

// 函数：添加边到邻接表
void add(int x, int y){
    E[++tot].to = y;        // 设置目标节点
    E[tot].next = h[x];     // 指向当前节点x的第一条边
    h[x] = tot;             // 更新节点x的第一条边索引
}

int tot1, tot2, h1[SIZE], h2[SIZE];

// 函数：添加玩家到t节点的列表
void add1(int x, int y)
{
    e1[++tot1].to = y;      // y表示玩家编号
    e1[tot1].next = h1[x];  // 链接当前节点x的玩家列表
    h1[x] = tot1;           // 更新节点x的玩家列表头
}

// 函数：添加玩家到LCA节点的列表
void add2(int x, int y){
    e2[++tot2].to = y;      // y表示玩家编号
    e2[tot2].next = h2[x];  // 链接当前节点x的玩家列表
    h2[x] = tot2;           // 更新节点x的玩家列表头
}

// 深度优先搜索，预处理深度和祖先节点
void dfs1(int x){
    // 预处理二进制提升表
    for(int i=1; (1<<i)<=deep[x]; i++)
        fa[x][i] = fa[fa[x][i-1]][i-1];
    
    // 遍历所有邻接节点
    for(int i=h[x]; i; i=E[i].next){
        int y = E[i].to;
        if(y == fa[x][0]) continue; // 避免回到父节点
        fa[y][0] = x;               // 设置y的直接父节点为x
        deep[y] = deep[x] + 1;      // 设置y的深度
        dfs1(y);                    // 递归DFS
    }
}

// 计算两个节点的最近公共祖先（LCA）
int get_lca(int x, int y){
    if(x == y) return x; // 如果两个节点相同，直接返回
    if(deep[x] < deep[y]) swap(x, y); // 确保x的深度不小于y
    
    // 将x提升到与y相同的深度
    int t = log(deep[x] - deep[y]) / log(2);
    for(int i=t; i>=0; i--){
        if(deep[fa[x][i]] >= deep[y])
            x = fa[x][i];
        if(x == y)
            return x;
    }
    
    // 同时提升x和y，找到LCA
    t = log(deep[x]) / log(2);
    for(int i=t; i>=0; i--){
        if(fa[x][i] != fa[y][i])
            x = fa[x][i], y = fa[y][i];
    }
    return fa[x][0];
}

int b1[SIZE*2], b2[SIZE*2], js[SIZE], dist[SIZE], s[SIZE], t_nodes[SIZE], l[SIZE], ans[SIZE];

// 第二次DFS，用于计算每个节点被观察到的玩家数量
void dfs2(int x){
    // 保存当前b1和b2的状态
    int t1 = b1[w[x] + deep[x]];
    int t2 = b2[w[x] - deep[x] + SIZE];
    
    // 遍历所有子节点
    for(int i=h[x]; i; i=E[i].next){
        int y = E[i].to;
        if(y == fa[x][0]) continue; // 避免回到父节点
        dfs2(y); // 递归DFS
    }
    
    // 更新b1和b2
    b1[deep[x]] += js[x];
    for(int i=h1[x]; i; i=e1[i].next){
        int y = e1[i].to;
        b2[dist[y] - deep[t_nodes[y]] + SIZE]++;
    }
    
    // 计算当前节点的答案
    ans[x] += b1[w[x] + deep[x]] - t1 + b2[w[x] - deep[x] + SIZE] - t2;
    
    // 恢复b1和b2的状态，避免影响其他分支
    for(int i=h2[x]; i; i=e2[i].next){
        int y = e2[i].to;
        b1[deep[s[y]]]--;
        b2[dist[y] - deep[t_nodes[y]] + SIZE]--;
    }
}

int main(){
    freopen("running.in","r",stdin);
    freopen("running.out","w",stdout);
    // 读取节点数n和玩家数m
    cin>>n>>m;
    
    // 读取n-1条边，构建树的邻接表
    for(int i=1; i<n; i++){
        int u, v;
        cin>>u>>v;
        add(u, v);
        add(v, u);
    }
    
    // 初始化根节点的深度和父节点
    deep[1] = 1;
    fa[1][0] = 1;
    dfs1(1); // 预处理深度和二进制提升表
    
    // 读取每个节点的观察时间Wj
    for(int i=1; i<=n; i++) cin>>w[i];
    
    // 读取m个玩家的信息
    for(int i=1; i<=m; i++){
        cin>>s[i]>>t_nodes[i];
        int lca = get_lca(s[i], t_nodes[i]); // 计算玩家的LCA
        dist[i] = deep[s[i]] + deep[t_nodes[i]] - 2 * deep[lca]; // 计算玩家的路径长度
        
        js[s[i]]++; // 统计每个起点有多少玩家
        add1(t_nodes[i], i); // 将玩家加入终点节点的列表
        add2(lca, i); // 将玩家加入LCA节点的列表
        
        // 如果LCA节点的深度加上Wj恰好等于起点的深度，减去该节点的答案
        if(deep[lca] + w[lca] == deep[s[i]]) ans[lca]--;
    }
    
    dfs2(1); // 计算每个节点被观察到的玩家数量
    
    // 输出每个节点的答案
    for(int i=1; i<=n; i++) 
    cout<<ans[i]<<' ';
    //printf("%d ", ans[i]);
    return 0;
}