2023NOIP A层联测27 A.kotori
题目大意
琴里的飞船中有 \(n\) 个人，其中有 \(n - 1\) 个通道，所以飞船的内部是一个树形结构。每个人从 \(1-n\) 编号，编号越小代表这个人的投票经验最丰富。
每个人有一个投票装置，初始都没有启动。现在琴里希望她的飞船支持 \(q\) 次操作，每次操作是以下两种行动之一：
- 把第 \(x\) 个人的投票装置启动。
- 由于每个人都想向经验最丰富的人咨询决策，但又不想绕路地去往一个装置前投票，所以还需要快速查询第 \(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);
}