无根树不好想钦定 00 为根转化成有根树。从 s 出发要么走向父亲要么走向某个儿子。需要通过标签判断 t 是否在某个儿子的子树内。容易想到记录每个点 u 对应的 dfn 区间 [,][lu​,ru​] 就能把子树关系转成区间包含关系。我们直接把 [,][lu​,ru​] 存进编号比如存 ×1000lu​×1000ru​。但是这样会有不少冗余。事实上只需要知道 lu​ 和所有儿子的 r或者反之就能确定子树结构。考虑交错存储奇数层存 l偶数层存 r。不过还有一个问题对于奇数层的点 urfau​​ 等于最后一个儿子的 r导致分不清这两个点。为何偶数层没有这个问题呢因为 lfau​​dfnfau​​不会等于第一个儿子的 l。这启发我们让所有偶数层的点 u 满足 ru​dfnu​。也就是奇数层前序 dfs偶数层后序 dfs。Code#include stations.h#include bits/stdc.h#define rep(i,a,b) for(int i(a);ib;i)#define rept(i,a,b) for(int i(a);ib;i)#define eb emplace_backusing namespace std;constexpr int N1e35;vectorint g[N],res;int d[N],cnt;void dfs(int u,int pre){ // 奇数层前序偶数层后序if(d[u]1) res[u]cnt;for(int v:g[u]) if(v^pre) d[v]d[u]1,dfs(v,u);if(~d[u]1) res[u]cnt;}vectorint label(int n,int k,vectorint u,vectorint v){res.resize(n),cnt0;rep(i,0,n) g[i].clear(),d[i]0;rep(i,0,u.size()) g[u[i]].eb(v[i]),g[v[i]].eb(u[i]);dfs(0,0);return res;}int find_next_station(int s,int t,vectorint c){if(c[0]s){sort(c.begin(),c.end());int fac.back(),lsts1;c.pop_back();for(int x:c){if(lstttx) return x;lstx1;}return fa;}else{sort(c.begin(),c.end(),greaterint());int fac.back(),lsts-1;c.pop_back();for(int x:c){if(xttlst) return x;lstx-1;}return fa;}}