UOJ #569. 【IOI2020】Stations

题面传送门
这种题到底叫啥……，给点编号传信息的题见过好几个了也不是交互也不是通信的……
首先显然有一个记录dfs序中子树起始点和终止点的东西，最大是\(O(n^2)\)的。
我们发现它给了我们所有相邻点的编号，这些点的编号不仅可以判断往哪个点走，还可以提供信息。
我们发现只要给定了一个点子树的起始位置，周围的点都是终止位置，那么就可以判断往哪边走。因为这个点子树的子树实际上已经可以计算。当给定一个点终止位置的时候也是如此。因此可以对树黑白染色，这样就可以做到\(2n\)的最大值。
这个\(2n\)是因为dfs序长度为\(2n\)，但是我们实际上只传过去\(n\)个数啊，所以把剩下\(n\)个扔了就好了也不改变相对顺序。
code:

#include "stations.h"
#include
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define ll long long
#define db double
#define lb long db
#define N (1000+5)
#define M (1000000+5)
#define K (20+5)
#define mod 1000000007
#define Mod (mod-1)
#define eps (1e-9)
#define U unsigned int
#define it iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) (n*(x-1)+(y))
#define R(n) (rand()*rand()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
using namespace std;
int col[N],H;vector W;vector S[N];
I void dfs(int x,int w,int La){col[x]=w;col[x]&&(W[x]=++H);for(int i:S[x]) i^La&&(dfs(i,w^1,x),0);!col[x]&&(W[x]=++H);}
std::vector label(int n, int k, std::vector u, std::vector v) {
	W.clear();int i;H=0;for(i=0;i c) {
	if(sLa&&t<=c[i]) return c[i];La=c[i];}return c[c.size()-1];
	}else{
		int La=s;for(int i=c.size()-1;i;i--) {if(t=c[i]) return c[i];La=c[i];}return c[0];
	}
}