首页 > 代码库 > Educational Codeforces Round 25 G. Tree Queries

Educational Codeforces Round 25 G. Tree Queries

2024-10-30 15:48:02   212人阅读

题目链接：Educational Codeforces Round 25 G. Tree Queries

题意：

给你一棵树，一开始所有的点全是黑色，有两种操作。

1 x 将x这个点变为黑色，保证第一个操作是这个。

2 x 询问x到任意黑色的点的简单路径上的最小节点编号。

题解：

首先将一个变为黑色的点当成树根，然后dfs一下，预处理出所有点的答案。

然后开一个变量记录一下当前变黑的点的答案cur=min(cur,dp[x])。

每次询问的时候答案就是min(cur,dp[x])。

如果觉得很神奇，自己模拟一遍就知道了。

技术分享 
 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=(a);i<=(b);++i)
 3 using namespace std;
 4 
 5 const int N=1e6+7;
 6 vector<int>g[N];
 7 int n,m,x,y,dp[N];
 8 
 9 void dfs(int x,int f)
10 {
11     dp[x]=min(x,dp[f]);
12     for(int &it:g[x])if(it!=f)dfs(it,x);
13 }
14 
15 int main(){
16     scanf("%d%d",&n,&m);
17     F(i,2,n)
18     {
19         scanf("%d%d",&x,&y);
20         g[x].push_back(y);
21         g[y].push_back(x);
22     }
23     dp[0]=N;
24     int last=0,cur=N;
25     F(i,1,m)
26     {
27         scanf("%d%d",&x,&y);
28         y=(y+last)%n+1;
29         if(x==1)
30         {
31             if(i==1)dfs(y,0);
32             cur=min(cur,dp[y]);
33         }else printf("%d\n",last=min(cur,dp[y]));
34     }
35     return 0;
36 }
View Code

 

Educational Codeforces Round 25 G. Tree Queries


联系
我们