2023NOIP A层联测27 A.kotori

联测27 A.kotori"/>

2023NOIP A层联测27 A.kotori

2023NOIP A层联测27 A.kotori

文章目录

• 2023NOIP A层联测27 A.kotori
• • 题目大意
  • 思路
  • code

题目大意

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

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

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

n , q ≤ 1 0 6 n , q \le 10^6 n,q≤106

思路

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

那么询问点 x x x 的答案就是：点 x 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);
}