【2019.10.7 CCF-CSP-2019模拟赛 T1】树上查询（tree）（思维）

思维

这道题应该算是一道思维题吧。

首先你要想到，既然这是一棵无根树，就要明智地选择根——以第一个黑点为根（不要像我一样习惯性以\(1\)号点为根，结果直到心态爆炸都没做出来）。

想到这一点，这题就很简单了。

具体

设\(p_i\)为从\(i\)到根路径上的最小值，考虑一个黑点\(y\)对于\(x\)号点的贡献。

显然这一贡献就是将\(x\)的答案向\(y\)到\(LCA(x,y)\)路径上的最小值取\(min\)。

而由于\(LCA(x,y)\)到根路径上的最小值也是\(x\)到根路径上的最小值，肯定会被算在答案中，所以就相当于是向\(y\)到根路径上的最小值，即\(p_y\)取\(min\)。

所以，我们开一个变量\(t\)，记录所有黑点\(p\)的最小值。

则\(x\)的答案就是\(min(p_x,t)\)。

代码

#include<bits/stdc++.h>

#define Tp template<typename Ty>

#define Ts template<typename Ty,typename... Ar>

#define Reg register

#define RI Reg int

#define Con const

#define CI Con int&

#define I inline

#define W while

#define N 1000000

#define add(x,y) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y)

#define Gmin(x,y) (x>(y)&&(x=(y)))

#define min(x,y) ((x)<(y)?(x):(y))

using namespace std;

int n,Qt,ee,lnk[N+5];struct edge {int to,nxt;}e[N<<1];

class FastIO

{

	private:

		#define FS 100000

		#define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++)

		#define pc(c) (C==E&&(clear(),0),*C++=c)

		#define tn (x<<3)+(x<<1)

		#define D isdigit(c=tc())

		int T;char c,*A,*B,*C,*E,FI[FS],FO[FS],S[FS];

	public:

		I FastIO() {A=B=FI,C=FO,E=FO+FS;}

		Tp I void read(Ty& x) {x=0;W(!D);W(x=tn+(c&15),D);}

		Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}

		Tp I void write(Ty x) {W(S[++T]=x%10+48,x/=10);W(T) pc(S[T--]);}

		Tp I void writeln(Con Ty& x) {write(x),pc('\n');}

		I void clear() {fwrite(FO,1,C-FO,stdout),C=FO;}

}F;

class Solver

{

	private:

		int p[N+5];

		I void dfs(CI x,CI lst=0)//初始化p

		{

			for(RI i=lnk[x];i;i=e[i].nxt) e[i].to^lst&&

				(p[e[i].to]=min(p[x],e[i].to),dfs(e[i].to,x),0);

		}

	public:

		I void Solve()

		{

			RI op,x,t,lst=0;F.read(op,x),--Qt,t=x%n+1,dfs(p[t]=t);//以第一个黑点为根

			W(Qt--) F.read(op,x),op==1?Gmin(t,p[(x+lst)%n+1]):(F.writeln(lst=min(t,p[(x+lst)%n+1])),0);//进行操作

		}

}S;

int main()

{

	freopen("tree.in","r",stdin),freopen("tree.out","w",stdout);

	RI i,x,y;for(F.read(n,Qt),i=1;i^n;++i) F.read(x,y),add(x,y),add(y,x);

	return S.Solve(),F.clear(),0;

}

巴特西

【2019.10.7 CCF-CSP-2019模拟赛 T1】树上查询（tree）（思维）

思维

具体

代码

最新文章

热门文章