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

DYYqwq · 2026-11-12 20:07:34 · 题解

P16359

只有图边具有不确定性，而且很少，对图边做 dp。

设 dp_{i,j,s} 表示当前走了 i 步，落在 j 号图边的左或右节点上的方案数。设 g_{i,s} 表示 i 号图边的左右节点。

尝试刻画路径，我们认为 g_{j,s} \rightarrow g_{k,t} 的路径应为：g_{j,s} \rightarrow 唯一确定的树边 \rightarrow g_{k,t \oplus1} \rightarrow g_{k,t}。

至于为什么这段路径要求走 k 这条图边而非 j，是因为这样转移恰好是上一步 j 走过图边。（题外话是，如果在转移中我们就是要走 j 而不是 k，可以尝试改变初始化和答案统计。）

因此我们有转移 dp_{i+dis(g_{j,s},g_{k,t \oplus1})+1,k,t} \leftarrow dp_{i,j,s}。

统计答案时，枚举最后一次走图边落到的位置，剩下的走树边。即 ans \leftarrow dp_{K-dis(n,g_{i,s}),i,s}。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 1e9 + 7;
struct edge {int to , nxt;}e[400010];
int n , m , K , tot , head[200010];
void add(int u , int v)
{
    ++ tot;
    e[tot].to = v;
    e[tot].nxt = head[u];
    head[u] = tot;
}
int fa[200010];
inline int get_fa(int x) {return fa[x] == x ? x : fa[x] = get_fa(fa[x]);}
int dep[200010] , Fa[200010][21];
int lca(int u , int v)
{
    if(dep[u] < dep[v]) swap(u , v);
    int d = dep[u] - dep[v];
    for(int i = 0 ; i <= 20 ; i ++)
    {
        if(d & 1) u = Fa[u][i];
        d >>= 1;
    }
    if(u == v) return v;
    for(int i = 20 ; i >= 0 ; i --)
    {
        if(Fa[u][i] == Fa[v][i]) continue;
        u = Fa[u][i] , v = Fa[v][i];
    }
    return Fa[u][0];
}
void dfs(int u , int pa)
{
    Fa[u][0] = pa , dep[u] = dep[pa] + 1;
    for(int i = 1 ; i <= 20 ; i ++) Fa[u][i] = Fa[Fa[u][i - 1]][i - 1];
    for(int i = head[u] ; i != 0 ; i = e[i].nxt)
    {
        int v = e[i].to;
        if(v == pa) continue;
        dfs(v , u);
    }
}
int Dis(int u , int v)
{
    int LCA = lca(u , v);
    return dep[u] + dep[v] - 2 * dep[LCA];
}
int graph[200010][2]; int cnt = 0;
ll dp[100010][13][2];
int main()
{
    scanf("%d%d%d" , &n , &m , &K); vector<pair<int , int>> E;
    for(int i = 1 ; i <= n ; i ++) fa[i] = i;
    for(int i = 1 , u , v ; i <= m ; i ++) scanf("%d%d" , &u , &v) , E.push_back({u , v});
    for(auto [u , v] : E)
    {
        int uu = get_fa(u) , vv = get_fa(v);
        if(uu != vv) add(u , v) , add(v , u) , fa[uu] = vv;
        else graph[++ cnt][0] = u , graph[cnt][1] = v;
    }
    dfs(1 , 0);
    graph[0][0] = graph[0][1] = 1;
    dp[0][0][1] = 1;
    for(int i = 0 ; i < K ; i ++)
    {
        for(int j = 0 ; j <= cnt ; j ++)
        {
            for(int k = 1 ; k <= cnt ; k ++)
            {
                for(int s = 0 ; s <= 1 ; s ++)
                {
                    for(int t = 0 ; t <= 1 ; t ++)
                    {
                        if(s != t && j == k) continue;
                        int p = i + Dis(graph[j][s] , graph[k][t ^ 1]) + 1;
                        if(p <= K) (dp[p][k][t] += dp[i][j][s]) %= mod;
                    }
                }
            }
        }
    }
    ll ans = 0;
    for(int i = 0 ; i <= cnt ; i ++)
    {
        for(int s = 0 ; s <= 1 ; s ++)
        {
            int p = K - Dis(n , graph[i][s]);
            if(p >= 0) ans += dp[p][i][s] , ans %= mod;
        }
    }
    printf("%lld" , ans);
    return 0;
}

细节是避免数组越界。

下面提供上文说的另一种写法。这种写法较为复杂，需要较为具体的初始化，以及加入只走树边的贡献。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 1e9 + 7;
struct edge {int to , nxt;}e[400010];
int n , m , K , tot , head[200010];
void add(int u , int v)
{
    ++ tot;
    e[tot].to = v;
    e[tot].nxt = head[u];
    head[u] = tot;
}
int fa[200010];
inline int get_fa(int x) {return fa[x] == x ? x : fa[x] = get_fa(fa[x]);}
int dep[200010] , Fa[200010][21];
int lca(int u , int v)
{
    if(dep[u] < dep[v]) swap(u , v);
    int d = dep[u] - dep[v];
    for(int i = 0 ; i <= 20 ; i ++)
    {
        if(d & 1) u = Fa[u][i];
        d >>= 1;
    }
    if(u == v) return v;
    for(int i = 20 ; i >= 0 ; i --)
    {
        if(Fa[u][i] == Fa[v][i]) continue;
        u = Fa[u][i] , v = Fa[v][i];
    }
    return Fa[u][0];
}
void dfs(int u , int pa)
{
    Fa[u][0] = pa , dep[u] = dep[pa] + 1;
    for(int i = 1 ; i <= 20 ; i ++) Fa[u][i] = Fa[Fa[u][i - 1]][i - 1];
    for(int i = head[u] ; i != 0 ; i = e[i].nxt)
    {
        int v = e[i].to;
        if(v == pa) continue;
        dfs(v , u);
    }
}
int Dis(int u , int v)
{
    int LCA = lca(u , v);
    return dep[u] + dep[v] - 2 * dep[LCA];
}
int graph[200010][2]; int cnt = 0;
ll dp[100010][13][2];
int main()
{
    scanf("%d%d%d" , &n , &m , &K); vector<pair<int , int>> E;
    for(int i = 1 ; i <= n ; i ++) fa[i] = i;
    for(int i = 1 , u , v ; i <= m ; i ++) scanf("%d%d" , &u , &v) , E.push_back({u , v});
    for(auto [u , v] : E)
    {
        int uu = get_fa(u) , vv = get_fa(v);
        if(uu != vv) add(u , v) , add(v , u) , fa[uu] = vv;
        else graph[++ cnt][0] = u , graph[cnt][1] = v;
    }
    dfs(1 , 0);
//  graph[0][0] = graph[0][1] = 1;
//  dp[0][0][0] = 1;
    for(int i = 1 ; i <= cnt ; i ++) dp[Dis(1 , graph[i][0])][i][0] = dp[Dis(1 , graph[i][1])][i][1] = 1; 
    for(int i = 0 ; i < K ; i ++)
    {
        for(int j = 1 ; j <= cnt ; j ++)
        {
            for(int k = 1 ; k <= cnt ; k ++)
            {
                for(int s = 0 ; s <= 1 ; s ++)
                {
                    for(int t = 0 ; t <= 1 ; t ++)
                    {
                        if(s != t && j == k) continue;
                        int p = i + Dis(graph[j][s ^ 1] , graph[k][t]) + 1;
                        if(p <= K) (dp[p][k][t] += dp[i][j][s]) %= mod;
                    }
                }
            }
        }
    }
    ll ans = 0;
    for(int i = 0 ; i <= cnt ; i ++)
    {
        for(int s = 0 ; s <= 1 ; s ++)
        {
            int p = K - Dis(n , graph[i][s ^ 1]) - 1;
            if(p >= 0) ans += dp[p][i][s] , ans %= mod;
        }
    }
    printf("%lld" , ans + (dep[n] == K + 1));
    return 0;
}