题解：P16359 [BalticOI 2026] Tourist's Journey

WYZqaq · 2026-11-12 19:22:36 · 题解

为啥这个题这么简单，模拟赛没写出来呢。

这个题的话，我们考虑图边之有 11 条，之后，很经典的想法就是把图边和树边分开考虑。

之后，我们设 dp_{i,j} 表示我们已经走了 i 步，强制最后一步走第 j 条图边（这个题是双向边，所以说我们把所有图边记录两次），之后呢，我们考虑这个 dp 如何转移，我们考虑到，一种不合法情况就是下一条边的编号（编号都是从 0 开始）是这一条边对应的反边，例如，我们从上一步 5 走到 3，下一步就不可以从 3 走到 5。因为我们不能反复经过同一条边，但是，比如说我们上一次走的图边是 5 到 3，下一次的图边也可以是 5 到 3，因为保证没有重边。所以说，下一次走 5 到 3 一定是经过其他路径的。

我们如何判断两条边互为反边呢。就是比如说两条边选的是 j 和 k，k=j \operatorname{xor} 1，因为是 0 为下标开头，加入相邻边的顺序就是相邻的，直接这么判断就行。

考虑 dp 转移，先给出转移式子 dp[i+dis(g[j].second,g[k].first)+1][k]=(dp[i+dis(g[j].second,g[k].first)+1][k]+dp[i][j])%mod; 解释这个式子，就是说，枚举 i 和 j 表示当前的步数和经过的边，k 表示下一次经过的边，dis 表示树上两点之间的距离，式子的话，就是从图边的尾走到下一条图边的头，再加上走这条图边的步数。

统计答案的话，就是枚举 i 和 j 表示最后一次走图边的步数和图边的编号，之后我们考虑，从当前图边的尾走到 n 的距离为 x，如果 x+i 和 k 相等的话，当前的 dp 就能被统计进答案。

之后不要忘记不走图边的贡献。就是在 dfs 中 dep_n 和 k 相等就是只走树的贡献（显然贡献为 1）。

没看懂看代码吧。

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
#define int long long
struct edge{
    int to,net;
}e[450005];
int tot=0;
int head[200005];
int fa[200005];
int u[450005];
int v[450005];
int vis[450005];
int dp[250005][31];
vector<pair<int,int> >g;
int dep[200005];
int f[200005][25];
void add(int u,int v){
    tot++;
    e[tot].to=v;
    e[tot].net=head[u];
    head[u]=tot;
}
int get_fa(int u){
    return (fa[u]==u?u:fa[u]=get_fa(fa[u]));
}
void dfs(int u,int pa){
    f[u][0]=pa;
    dep[u]=dep[pa]+1;
    for(int i=head[u];i;i=e[i].net){
        if(e[i].to!=pa){
            dfs(e[i].to,u);
        }
    }
}
int lca(int x,int y){
    if(dep[x]<dep[y]){
        swap(x,y);
    }
    int dick=dep[x]-dep[y];
    for (int i=0; i <=20; i++)
    {
        if(dick&(1<<i)){
            x=f[x][i];
        }
    }
    if(x==y){
        return x;
    }
    for(int i=20;i>=0;i--){
        if(f[x][i]!=f[y][i]){
            x=f[x][i];
            y=f[y][i];
        }
    }
    return f[x][0];
}
int dis(int u,int v){
    return dep[u]+dep[v]-2*dep[lca(u,v)];
}
main(){
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
    for(int i=1;i<=m;i++){
        cin>>u[i]>>v[i];
    }
    for(int i=1;i<=m;i++){
        int uu=get_fa(u[i]);
        int vv=get_fa(v[i]);
        if(uu!=vv){
            add(u[i],v[i]);
            add(v[i],u[i]);
            fa[uu]=vv;
        }
        else{
            g.push_back({u[i],v[i]});
            g.push_back({v[i],u[i]});
        }
    }//建树
    dfs(1,0);
    for(int j=1;j<=20;j++){
        for(int i=1;i<=n;i++){
            f[i][j]=f[f[i][j-1]][j-1];
        }
    }
    if(!g.size()){//当时忘记加没走图边的贡献，调了很长时间
        cout<<(dep[n]==k+1?1:0);
        return 0;
    }
    for(int j=0;j<g.size();j++){
        dp[dis(1,g[j].first)+1][j]=1;
    }
    for(int i=0;i<k;i++){//计数
        for(int j=0;j<g.size();j++){
            for(int k=0;k<g.size();k++){
                if(k==(j^1)){
                    continue;
                }
                dp[i+dis(g[j].second,g[k].first)+1][k]=(dp[i+dis(g[j].second,g[k].first)+1][k]+dp[i][j])%mod;
            }
        }
    }
    int ans=0;
    for(int i=0;i<g.size();i++){//统计答案
        int x=g[i].second;
        if(k<dis(n,x))continue;
        ans=(ans+dp[k-dis(n,x)][i])%mod;
    }
    cout<<ans+(dep[n]==k+1?1:0);
    return 0;
}