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 <bits/stdc++.h>
#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);
}