2023NOIP A层联测27 A.kotori

2023NOIP A层联测27 A.kotori

题目大意

琴里的飞船中有 $n$ 个人，其中有 $n-1$ 个通道，所以飞船的内部是一个树形结构。每个人从 $1-n$ 编号，编号越小代表这个人的投票经验最丰富。

每个人有一个投票装置，初始都没有启动。现在琴里希望她的飞船支持 $q$ 次操作，每次操作是以下两种行动之一：

1. 把第 $x$ 个人的投票装置启动。
2. 由于每个人都想向经验最丰富的人咨询决策，但又不想绕路地去往一个装置前投票，所以还需要快速查询第 $x$ 个人到任意一个投票装置的简单路径上的编号最小的人。

$n,q\le 10^6$

思路

我们以第一个激活的点为根。

那么询问点 $x$ 的答案就是：点 $x$ 到根的最小值或者所有已激活的点到根的最小值。

code

#include 
#define fu(x , y , z) for(int x = y ; x <= z ; x ++) 
using namespace std;
const int N = 1e6 + 5;
int flg[N] , sz[N] , hd[N] , cnt , dis[N];
struct E {
    int to , nt;
} e[N << 1];
void add (int x , int y) { e[++cnt].to = y , e[cnt].nt = hd[x] , hd[x] = cnt; }
void dfs1 (int x , int fa) {
    sz[x] = flg[x];
    int max1 = 0 , y;
    for (int i = hd[x] ; i ; i = e[i].nt) {
        y = e[i].to;
        if (y == fa) continue;
        dfs1 (y , x);
        dis[x] += dis[y] + sz[y];
        sz[x] += sz[y];
        
    }
}
int main () {
    int u , v;
    scanf ("%d" , &n);
    fu (i , 1 , n) scanf ("%1d" , &flg[i]);
    fu (i , 1 , n - 1) {
        scanf ("%d%d" , &u , &v);
        add (u , v) , add (v , u);
    }
    dfs1 (1 , 0);
}
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