题解：P16445 [XJTUPC 2026] The Whole Rest
ran_qwq
·
·
题解
赛时首杀。
如果一条路径起点为 s 终点为 t，拉出 s 到 t 的简单路径。因为是树，所以不在 s 到 t 路径上的边一定经过偶数次，即路径的代价为起点到终点简单路径的异或和。
考虑一条回路，路径的代价为 0，所以最小值一定是 0。当确定了起点和终点，最优路径一定是从起点走到终点，途中按 dfs 序遍历不在简单路径上的点。
令 $D_u=\operatorname{dis}(1,u)$，要求找最长的、$D_s=D_t$ 的 $(s,t)$。把 $D$ 相同的点放到一起，又转化为找每个 $D$ 值虚树的直径。直接对每个 $D$ 值找离 $1$ 最远的点，再找离这个点最远的点即可。
:::info[代码]
```cpp
#include<bits/stdc++.h>
#define il inline
#define ui unsigned int
#define ll long long
#define ull unsigned ll
#define lll __int128
#define db double
#define ldb long double
#define pii pair<int,int>
#define vi vector<int>
#define vpii vector<pii>
#define fir first
#define sec second
#define gc getchar
#define pc putchar
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define pct __builtin_popcount
#define mst(a,x) memset(a,x,sizeof a)
#define mcp(a,b) memcpy(a,b,sizeof b)
using namespace std;
const int N=5e5+10,INF=0x3f3f3f3f,MOD=998244353;
const ll INFll=0x3f3f3f3f3f3f3f3f;
il int rd() {int x=0,f=1; char ch=gc(); while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=gc();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc(); return x*f;}
il ll rdll() {ll x=0; int f=1; char ch=gc(); while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=gc();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc(); return x*f;}
il void wr(int x) {if(x==INT_MIN) return printf("-2147483648"),void(); if(x<0) return pc('-'),wr(-x); if(x<10) return pc(x+'0'),void(); wr(x/10),pc(x%10+'0');}
il void wrll(ll x) {if(x==LLONG_MIN) return printf("-9223372036854775808"),void(); if(x<0) return pc('-'),wrll(-x); if(x<10) return pc(x+'0'),void(); wrll(x/10),pc(x%10+'0');}
il void wr(int x,const char *s) {wr(x),printf("%s",s);}
il void wrll(ll x,const char *s) {wrll(x),printf("%s",s);}
il int vmod(int x) {return x>=MOD?x-MOD:x;}
il int vadd(int x,int y) {return vmod(x+y);}
il int vsub(int x,int y) {return vmod(x-y+MOD);}
il int vmul(int x,int y) {return 1ll*x*y%MOD;}
il int qpow(int x,int y) {int r=1; for(;y;y>>=1,x=vmul(x,x)) if(y&1) r=vmul(r,x); return r;}
il void cadd(int &x,int y) {x=vmod(x+y);}
il void csub(int &x,int y) {x=vmod(x-y+MOD);}
il void cmul(int &x,int y) {x=vmul(x,y);}
il void cmax(int &x,int y) {x<y&&(x=y);}
il void cmaxll(ll &x,ll y) {x<y&&(x=y);}
il void cmin(int &x,int y) {x>y&&(x=y);}
il void cminll(ll &x,ll y) {x>y&&(x=y);}
int n,id=1,mn=INF,hd[N],ds[N],ac[N][20],d[N];
struct EDGE {int to,w,ne;} e[N*2];
il void add(int u,int v,int w) {e[++id]={v,w,hd[u]},hd[u]=id;}
void dfs1(int u,int fa) {
ac[u][0]=fa,d[u]=d[fa]+1;
for(int i=1;i<20;i++) ac[u][i]=ac[ac[u][i-1]][i-1];
for(int i=hd[u],v;i;i=e[i].ne) if((v=e[i].to)!=fa)
ds[v]=ds[u]^e[i].w,dfs1(v,u);
}
int ln,dd[N],ps[N],md[N];
vi vc[N];
int lca(int u,int v) {
if(d[u]<d[v]) swap(u,v);
for(int i=19;~i;i--) if(d[ac[u][i]]>=d[v]) u=ac[u][i];
if(u==v) return u;
for(int i=19;~i;i--) if(ac[u][i]!=ac[v][i]) u=ac[u][i],v=ac[v][i];
return ac[u][0];
}
int as=-1,s,t,bk[N],fg[N*2];
void dfs2(int u,int fa) {
bk[u]=u==t;
for(int i=hd[u],v;i;i=e[i].ne) if((v=e[i].to)!=fa) {
dfs2(v,u);
if(bk[v]) bk[u]=1,fg[i]=fg[i^1]=1;
}
}
vi sq;
void dfs3(int u,int fa) {
sq.pb(u);
for(int i=hd[u],v;i;i=e[i].ne) if((v=e[i].to)!=fa&&!fg[i]) dfs3(v,u),sq.pb(u);
for(int i=hd[u],v;i;i=e[i].ne) if((v=e[i].to)!=fa&&fg[i]) dfs3(v,u);
}
void QwQ() {
n=rd();
for(int i=1,u,v,w;i<n;i++) u=rd(),v=rd(),w=rd(),add(u,v,w),add(v,u,w);
dfs1(1,0);
for(int i=1;i<=n;i++) dd[i]=ds[i];
sort(dd+1,dd+1+n),ln=unique(dd+1,dd+1+n)-dd-1;
for(int i=1;i<=n;i++) {
int x=lb(dd+1,dd+1+ln,ds[i])-dd;
vc[x].pb(i);
if(md[x]<d[i]+1) md[x]=d[i]+1,ps[x]=i;
}
for(int i=1;i<=ln;i++) {
int u=ps[i],x=lb(dd+1,dd+1+ln,ds[u])-dd;
for(int j:vc[x]) {
int cr=d[u]+d[j]-d[lca(u,j)]*2;
if(as<cr) as=cr,s=u,t=j;
}
}
dfs2(s,0),dfs3(s,0);
if(sq.back()!=t) sq.pb(t);
wr(sq.size(),"\n");
for(int x:sq) wr(x," ");
}
signed main() {
// freopen("in.in","r",stdin),freopen("out.out","w",stdout);
int T=1; while(T--) QwQ();
}
/*
4
1 2 0
2 3 0
2 4 1
*/
```
:::