分身游走

看到 k≤30k \le 30 ，就大概想到是个关于 kk 的 DP, 然而太菜了当时连暴力 DP 都写不出来。

观察性质：

  1. 在最优方案中，一定不会出现超过一个分身进入以 xx 为根的子树又回到 xx 的父亲的情况。

  2. 在最优方案中，如果有至少两个分身进入了以 xx 为根的子树，那么这些分身都应该停在以 xx 为根的子树内。

用这两条性质可以将 DP 优化到 O(n2k2)O(n^2k^2)。

这个 DP 需要枚举出发点，重新计算以每个点为根的子树的 DP 值，但是其中有不少重复计算。

我们可以枚举每一条边 (x,y)(x,y), 计算以 yy 为父节点，xx 为根的子树的 DP 值，并在之后的 DP 中重复利用。

这样我们枚举出发点时只需要将所有儿子的答案合并起来即可。

然而这个算法的时间复杂度又是与点的度数有关的，可以用三度化保证时间复杂度为 O(nk2)O(nk^2)。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
struct Rhine_Lab {
    Rhine_Lab()
    {
        freopen("move.in", "r", stdin);
        freopen("move.out", "w", stdout);
    }
};
Rhine_Lab Ptilopsis_w;

const int INF = 0x3f3f3f3f;
const int N = 300005;

namespace graph {
    struct edge {
        int to, cost, next;
    } e[N];
    int head[N], ecnt = 1;
    void add_edge(int a, int b, int w);
}
using namespace graph;

int n, k, tot;
vector<edge> ver[N];
int f[N][35], ans[35], id[N];

void build(int x);
void solve(int x, int pre);

int main()
{
    cin >> n >> k;
    memset(f, 0x3f, sizeof(f));
    for(int i = 1, u, v, w; i < n; i++)
    {
        cin >> u >> v >> w;
        ver[u].push_back({v, w});
        ver[v].push_back({u, w});
    }
    build(1);
    for(int i = 2; i <= ecnt; i++)
        solve(e[i].to, i);
    for(int rt = 1; rt <= n; rt++)
    {
        int x = id[rt]; ans[0] = 0;
        for(int i = head[x]; i; i = e[i].next)
        {
            for(int l = k; l >= 1; l--)
            {
                ans[l] += f[i][0]+e[i].cost*2;
                for(int j = 1; j <= l; j++)
                    ans[l] = min(ans[l], ans[l-j]+f[i][j]+e[i].cost*j);
            }
            ans[0] += f[i][0]+e[i].cost*2;
        }
        for(int i = 1; i <= k; i++)
            ans[i] = min(ans[i], ans[i-1]);
        cout << ans[k] << "\n";
    }
}

void build(int x)
{
    id[x] = ++tot;
    int u = id[x];
    
    for(auto i : ver[x])
    {
        if(id[i.to]) continue;
        ++tot;
        add_edge(u, tot, 0); u = tot;
        add_edge(u, tot+1, i.cost);
        build(i.to);
    }
}
void solve(int x, int pre)
{
    if(f[pre][0] != INF)
        return void();
    f[pre][0] = 0;
    for(int i = head[x]; i; i = e[i].next)
    {
        if(i == (pre^1)) continue;
        solve(e[i].to, i);
        for(int j = k; j >= 1; j--)
        {
            int tmp = INF;
            for(int k = 0; k <= j; k++)
                tmp = min(tmp, f[pre][j-k]+f[i][k]+e[i].cost*(k?k:2));
            f[pre][j] = tmp;
        }
        f[pre][0] += f[i][0]+e[i].cost*2;
    }
    for(int i = 1; i <= k; i++)
        f[pre][i] = min(f[pre][i], f[pre][i-1]);
}

namespace graph {
    void add_edge(int a, int b, int c)
    {
        e[++ecnt] = {b, c, head[a]}; head[a] = ecnt;
        e[++ecnt] = {a, c, head[b]}; head[b] = ecnt;
    }
}

迷梦深层

看见这个邻接矩阵做乘法就大概知道是个什么东西了。

如果是普通邻接矩阵，把乘法换成加法，把加法换成取 min⁡\min，求的其实就是最短路。

但是这是个布尔矩阵，所以 Ai,jA_{i,j} 其实是 ii 是否能到达 jj。

而 Ai,jkA^k_{i,j} 代表 ii 在正好走 kk 条边的情况下是否能到达 jj 。

如果出现周期那么一定是进入了一个环或者走到了尽头。

然而有很多复杂的情况: 环套环，菊花图连环，环连链等等。

这时候有一个结论：一个强连通分量的周期等于强连通分量中所有环长度的 gcd⁡\gcd，证明不会，爬了。

显然整张图的周期就是所有强连通分量周期的 lcm⁡\operatorname{lcm}。

但是如何求出一个强连通分量的所有环？

我们可以在强连通分量中任选一个点作为根，整出一棵 dfs 树来，这样一条返祖边就代表一个环，一条横叉边就代表两个环的长度差，用非树边链接的两个点的深度差求 gcd⁡\gcd 就可以求出一个强连通分量的周期了。

求出 dd 之后考虑求 kk ，因为只有 n≤200n \le 200 的数据需要求 kk ，所以可以直接上倍增或者二分求出来 kk

( stop learning useless algorithms, go and solve some problems, learn how to use binary search

还有一个问题是需要在取模意义下求出 dd ，你可以用埃氏筛来求出每个数的所有质因子，我的做法比较暴力，直接用 map 启发式合并艹过去了。

#include <bits/stdc++.h>
using namespace std;
struct Rhine_Lab {
    Rhine_Lab()
    {
        freopen("lost.in", "r", stdin);
        freopen("lost.out", "w", stdout);
    }
};
Rhine_Lab Ptilopsis_w;
namespace Matrix {
    int lim;
    struct matrix {
        bool a[205][205];
        matrix() { memset(a, 0, sizeof(a)); }
        bool& operator() (int x, int y) { return a[x][y];}
        void init() { for(int i = 1; i <= lim; i++) a[i][i] = 1; }
    };

    matrix operator* (const matrix &A, const matrix &B)
    {
        matrix C;
        for(int i = 1; i <= lim; i++)
            for(int j = 1; j <= lim; j++)
                for(int k = 1; k <= lim; k++)
                    C.a[i][j] |= A.a[i][k]&B.a[k][j];
        return C;
    }
    matrix& operator*= (matrix &A, const matrix &B)
    {
        return A = A*B;
    }
    bool operator== (const matrix &A, const matrix &B)
    {
        for(int i = 1; i <= lim; i++)
            for(int j = 1; j <= lim; j++)
                if(A.a[i][j] != B.a[i][j]) return false;
        return true;
    }
    bool operator!= (const matrix &A, const matrix &B)
    {
        return !(A == B);
    }
    matrix qpow(matrix a, long long b)
    {
        matrix ans; ans.init();
        for(; b; b >>= 1, a *= a)
            if(b&1) ans = ans*a;
        return ans;
    }
}
using namespace Matrix;

typedef long long ll;
const int N = 1e5+10;
const int M = 2e5+10;
const int P = 1e9+7;

namespace graph {
    struct edge {
        int to, next;
    } e[M];
    int head[N], ecnt = 1;
    int dfn[N], low[N], dft;
    int scc[N], scc_tot;
    bool vis[N]; int dis[N];
    int cycle[N];
    map<ll,ll> pri[N];
    void tarjan(int x);
    void dfs(int x, int col);
    void add_edge(int a, int b);
}
using namespace graph;

ll d, k;
int n, m, t;
matrix A, Ad;
map<ll,ll> dpri;

ll getk();
void merge(map<ll,ll> &a, map<ll,ll> &b);
ll qpow(ll a, ll b);

signed main()
{
    scanf("%d%d%d", &n, &m, &t);
    for(int i = 1; i <= m; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add_edge(a, b);
    }
    for(int i = 1; i <= n; i++)
        if(!dfn[i]) tarjan(i);

    for(int i = 1; i <= n; i++)
        if(!vis[i]) dfs(i, scc[i]);

    for(int i = 1; i <= scc_tot; i++)
    {
        if(!cycle[i]) continue;
        int tmp = cycle[i];
        map<ll,ll> pri;
        for(int j = 2; j*j <= tmp; j++)
        {
            while(tmp%j == 0)
                pri[j]++, tmp /= j;
        }
        if(tmp != 1) pri[tmp] = 1;
        merge(dpri, pri);
    }
    d = 1;
    for(auto i : dpri)
        (d *= qpow(i.first, i.second)) %= P;

    if(t == 1) cout << getk() << " ";
    cout << d;

}

void merge(map<ll,ll> &a, map<ll,ll> &b)
{
    if(a.size() < b.size()) swap(a, b);
    for(auto i : b) a[i.first] = max(a[i.first], i.second);
}
ll qpow(ll a, ll b)
{
    ll ans = 1;
    for(; b; b >>= 1, a = a*a)
        if(b&1) ans = ans*a;
    return ans;
}

matrix pw[21];
ll getk()
{
    Matrix::lim = n;
    for(int x = 1; x <= n; x++)
        for(int i = head[x]; i; i = e[i].next)
            A(x, e[i].to) = 1;
    Ad = A;
    for(auto i : dpri)
        Ad = qpow(Ad, qpow(i.first, i.second));
    
    pw[0] = A;
    for(int i = 1; i <= 20; i++)
        pw[i] = pw[i-1]*pw[i-1];
    
    
    ll ans = 0, step = 0;
    matrix now, tmp;
    now.init();

    while(tmp = now*pw[step], tmp != tmp*Ad)
    {
        now = tmp;
        (ans += qpow(2, step)) %= P;
        step++;
        
    }
    for(int i = step; i >= 0; i--)
    {
        tmp = now*pw[i];
        if(tmp != tmp*Ad)
        {
            now = tmp;
            (ans += qpow(2, i)) %= P;
        }
    }
    
    return ans+1;
}

namespace graph {
    stack<int> st;
    void tarjan(int x)
    {
        dfn[x] = low[x] = ++dft;
        st.push(x);
        for(int i = head[x]; i; i = e[i].next)
        {
            int y = e[i].to;
            if(!dfn[y])
            {
                tarjan(y);
                low[x] = min(low[x], low[y]);
            }
            else if(!scc[y])
                low[x] = min(low[x], dfn[y]);
        }
        if(dfn[x] == low[x])
        {
            scc_tot++;
            while(st.size())
            {
                int a = st.top(); st.pop();
                scc[a] = scc_tot;
                if(a == x) break;
            }
        }
    }
    void dfs(int x, int col)
    {
        vis[x] = true;
        for(int i = head[x]; i; i = e[i].next)
        {
            int y = e[i].to;
            if(scc[y] != col) continue;
            if(!vis[y])
            {
                dis[y] = dis[x]+1;
                dfs(y, col);
            }
            else
            {
                if(!cycle[col]) cycle[col] = abs(dis[x]-dis[y]+1);
                else cycle[col] = __gcd(cycle[col], abs(dis[x]-dis[y]+1));
            }
        }
    }
    void add_edge(int a, int b)
    {
        e[++ecnt] = {b, head[a]}; head[a] = ecnt;
    }
}