题解：P16445 [XJTUPC 2026] The Whole Rest

· · 题解

如果对各类技巧熟悉的话应该可以轻松通过的一道题目。

首先注意到，从树上任意一点出发并回到自身的途径的边权异或和总是 0，所以答案至多是 2(n-1)。同时，如果一条边被经过了至少 3 次，那将其经过次数减少两次，由于这条边两端的点的度数奇偶性不变，所以总是还能构造出一条欧拉路径。因此，所有边经过次数不超过两次。

注意到在这样一条路径中，把仅经过一次的路径拿出来必然是一条链，则我们希望这条链的边权异或和为 0，在此基础上越长越好。对于这种问题，我们可以记每个点 u 到点 1 的链上所有边的边权异或和为 dis(u)，特别的，dis(1) = 0。这样，点 u 到点 v 的路径的边权异或和为 0，等价于 dis(u) = dis(v)。问题转化为找出 dis 相同的点中距离最远的一对。

一种做法是，借鉴树的直径的 DFS 求法：任选一个点 u，找到离 u 最远的点 v，再找到离 v 最远的点 w，则 (v,w) 是一条直径。这里对于每一组可以进行类似的操作，不过找最远点不能通过 DFS，而是通过 lca 解决。时间复杂度 O(n \log n)。

::::success[参考实现]

#include<bits/stdc++.h>
using namespace std;
const int Maxn=500000,Maxw=20;
int n,m=-1,lg[Maxn+10];
vector<vector<pair<int,int> > > adj;
map<int,int> mp;
vector<vector<int> > p;
pair<int,int> res={1,1};
int maxd=0;
vector<int> ans;
struct node
{
    int dep,val,nxt,fa[Maxw+2];
}nums[Maxn+10];
void dfs(int u,int fa)
{
    if(mp.find(nums[u].val)==mp.end()) m++,mp[nums[u].val]=m,p.push_back({u});
    else p[mp[nums[u].val]].push_back(u);
    for(int i=1;i<=lg[nums[u].dep];i++)
        nums[u].fa[i]=nums[nums[u].fa[i-1]].fa[i-1];
    for(pair<int,int> v:adj[u])
    {
        if(v.first==fa) continue;
        nums[v.first].dep=nums[u].dep+1;
        nums[v.first].val=nums[u].val^v.second;
        nums[v.first].fa[0]=u;
        dfs(v.first,u);
    }
    return;
}
int lca(int u,int v)
{
    if(nums[u].dep>nums[v].dep) swap(u,v);
    while(nums[v].dep>nums[u].dep)
        v=nums[v].fa[lg[nums[v].dep-nums[u].dep]];
    if(u==v) return u;
    for(int i=lg[nums[u].dep];i>=0;i--)
        if(i<=lg[nums[u].dep]&&nums[u].fa[i]!=nums[v].fa[i]) u=nums[u].fa[i],v=nums[v].fa[i];
    return nums[u].fa[0];
}
int dis(int u,int v){return nums[u].dep+nums[v].dep-(nums[lca(u,v)].dep<<1);}
void tag(int u,int v)
{
    int l=lca(u,v);
    while(u!=l)
        nums[u].nxt=nums[u].fa[0],u=nums[u].fa[0];
    while(v!=l)
        nums[nums[v].fa[0]].nxt=v,v=nums[v].fa[0];
    return;
}
void print(int u,int fa)
{
    ans.push_back(u);
    for(pair<int,int> v:adj[u])
    {
        if(v.first==nums[u].nxt||v.first==fa) continue;
        print(v.first,u);
        ans.push_back(u);
    }
    if(nums[u].nxt!=0) print(nums[u].nxt,u);
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    adj.resize(n+5);
    for(int i=1,u,v,w;i<n;i++)
    {
        cin>>u>>v>>w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    lg[1]=0;
    for(int i=2;i<=n;i++)
        lg[i]=lg[i>>1]+1;
    nums[1].dep=0,nums[1].val=0;
    dfs(1,0);
    for(int i=0,u,v,d,mx;i<=m;i++)
    {
        u=p[i][0],mx=0;
        for(int x:p[i])
        {
            d=dis(p[i][0],x);
            if(d>mx) u=x,mx=d;
        }
        v=u,mx=0;
        for(int x:p[i])
        {
            d=dis(u,x);
            if(d>mx) v=x,mx=d;
        }
        if(mx>maxd) res={u,v},maxd=mx;
    }
    tag(res.first,res.second);
    print(res.first,0);
    cout<<ans.size()<<"\n";
    cout<<ans[0];
    for(int i=1;i<int(ans.size());i++)
        cout<<" "<<ans[i];
    cout<<"\n";
    return 0;
}

::::