Znzryb's Blog

START206——Min Steps

Posted on 2025-10-03 Edited on 2026-04-06

思路讲解

你可以发现，这个式子可以写成这样：

$2^{c_1}+2^{c_2}$

AC代码

源代码

心路历程（WA，TLE，MLE……）

2025 CCPC 全国邀请赛（南昌）暨第二届江西省赛——D. 挑战图同构（分量哈希）

Posted on 2025-09-28 Edited on 2026-04-06

思路讲解

当然，我们首先看到这道题目，会想到暴力。

但是暴力显然不行，先不管这个东西要怎么求，存储上，你存都存不下来。

既然这个暴力是不行的，我们就想到，这个图上面的路径太多了，有什么东西两点之间只有一条路径呢？其实就是树。

那么这种比较复杂的题目，特别是比较复杂的图论题目，一般都要划分阶段。

因此我们就要想，这个，如何把这节点一点一点的加入这个图当中？

可以的，兄弟，是可以的。

我们假设我们现在有一张图，我们可以先把到这张图距离为 i 的点加入进来，再把 i+1 的点加入进来，… 。

我们可以使用 kruskal 进行实现，kruskal 的基本过程就是按从小到大排序，加入到图中，使用并查集判环。

划分阶段其实也很简单，就是两张图把距离为 i 的点加入进来，停住。干一些事情，再继续加入距离为 i+1 的点，… 。

我们把一个中间状态摘出来看，如果原来的图是一样的（同构的），加入进来的点的并查集划分是一样的，那么两张图就是同构的。

这么说有点抽象。比如说蓝色的点是原来的图，红色的点是新加进来的点，不难发现，这两张图是同构的。因为只要并查集划分相同，新点之间的这个 dis 就是 i，老点到新点之间的 dis 也都是 i。

然后我们就来到了最后一个问题，怎么样快速判断（ $O(1)$ ）两个图的并查集划分是相同的那？呃，其实不是那么难的。我们请出我们的老盆友，哈希。

一个联通块的签名可以理解为有什么点。有什么点的话，我们可以给每个点整一个随机值（mt19937_64），然后一个联通块有什么点，就相当于其所有拥有的点的随机值的异或起来。

把这个好几个联通块组合（异或）起来，就可以得到目前的这个并查集划分状态，然后直接比较这个哈希值即可。

AC代码

https://qoj.ac/submission/1415583

源代码

// by Gospel_rock
#include <algorithm>
#include <functional>
#include <random>
#include <vector>
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o << 1)
#define rson(o) (o << 1 | 1)
#define SZ(a) ((long long)a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var << ":" << var << "\n";
#define cend cerr << "\n-----------\n"
#define fsp(x) fixed << setprecision(x)
#define minn(vec) *min_element(vec.begin(), vec.end())
#define maxx(vec) *max_element(vec.begin(), vec.end())

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using pdd = pair<DB, DB>;
using plb = pair<ll, bool>;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using vb = vector<bool>;
using tll = tuple<ll, ll, ll>;
using vii = vector<int>;
using vpll = vector<pll>;
using vtll = vector<tll>;
using vdb = vector<DB>;
using vc = vector<char>;
using arr3 = array<ll, 3>;
using arr2 = array<ll, 2>;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e5 + 10,
                    INF = (ll)1e17 + 3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod = (ll)1e9 + 7;  // 998244353;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
const ll PI = ll(pi * 2e18) + 71;
ll N, M1, Q, X, K, T, lT, M2;
struct Edge {
    ll u, v, w;
    // bool operator<(const Edge &other) const {
    //     return w>other.w;
    // }
};
mt19937_64 rng(time(0));
ll rnd[MAXN];
hash<ll> hasher;
const ll RAN = rng();
ll mix(ll a, ll b) {
    ll res = (a ^ (b * RAN)) * PI;
    return res;
}
struct DSU {
    vll fa;
    ll N;
    vll siz;
    ll S;
    vll Sum;
    void resize(ll n) {
        this->N = n;
        fa.resize(N + 5);
        siz.resize(N + 5);
        Sum.resize(N + 5);
        S = 0;
        FOR(i, 1, N) {
            fa[i] = i;
            siz[i] = 1;
            Sum[i] = rnd[i];
            S ^= mix(Sum[i], siz[i]);
        }
    }
    ll find(ll x) {
        if (x == fa[x])
            return x;
        return fa[x] = find(fa[x]);
    }
    void merge(ll a, ll b) {
        ll faa = find(a), fab = find(b);
        if (faa == fab) return;
        S ^= mix(Sum[faa], siz[faa]);
        S ^= mix(Sum[fab], siz[fab]);
        fa[faa] = fab;
        siz[fab] += siz[faa];
        Sum[fab] ^= Sum[faa];
        S ^= mix(Sum[fab], siz[fab]);
        return;
    }
};
struct Solve {
    vll fa;
    vector<Edge> edge1, edge2;
    vll li;
    vector<vector<Edge>> g1;
    vector<vector<Edge>> g2;
    ll get(ll x) {
        ll res = lower_bound(all(li), x) - li.begin();
        return res;
    }
    DSU a, b;
    Solve() {
        cin >> N >> M1 >> M2;
        fa.resize(N + 5);
        edge1.resize(M1);
        edge2.resize(M2);
        a.resize(N);
        b.resize(N);
        FOR(i, 1, N) { fa[i] = i; }
        FOR(i, 1, M1) {
            ll u, v, w;
            cin >> u >> v >> w;
            edge1[i - 1] = {u, v, w};
            li.PB(w);
        }
        FOR(i, 1, M2) {
            ll u, v, w;
            cin >> u >> v >> w;
            edge2[i - 1] = {u, v, w};
            li.PB(w);
        }
        // sort(all(edge1));
        // sort(all(edge2));
        sort(all(li));
        li.resize(unique(all(li)) - li.begin());
        g1.resize(SZ(li) + 5);
        g2.resize(SZ(li) + 5);
        FOR(i, 1, M1) { g1[get(edge1[i - 1].w)].PB(edge1[i - 1]); }
        FOR(i, 1, M2) { g2[get(edge2[i - 1].w)].PB(edge2[i - 1]); }
        FOR(i, 0, SZ(li) - 1) {
            for (auto [u, v, w] : g1[i]) {
                a.merge(u, v);
            }
            for (auto [u, v, w] : g2[i]) {
                b.merge(u, v);
            }
            if (a.S != b.S) {
                cout << "NO\n";
                return;
            }
        }
        cout << "YES\n";
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> lT;
    FOR(i, 0, MAXN - 5) { rnd[i] = rng(); }
    while (lT--)
        Solve a;
    return 0;
}
/*
AC
https://qoj.ac/submission/1415583

*/

心路历程（WA，TLE，MLE……）

merge 的逻辑比较复杂，容易写错，之后可以使用，Old，New，这样的命名，避免混淆。

void merge(ll a, ll b) {
    ll faa = find(a), fab = find(b);
    if (faa == fab) return;
    S ^= mix(Sum[faa], siz[faa]);
    S ^= mix(Sum[fab], siz[fab]);
    fa[faa] = fab;
    siz[fab] += siz[faa];
    Sum[fab] ^= Sum[faa];
    S ^= mix(Sum[fab], siz[fab]);
    return;
}

2025 CCPC 全国邀请赛（南昌）暨第二届江西省赛———B. 精神胜利（位集bfs）

Posted on 2025-09-27 Edited on 2026-04-06

思路讲解

dij 不能用，因为边太多了。

因为边权只有0 和 1，可以使用位集 bfs。

AC代码

https://qoj.ac/submission/1411426

判断一下是否可以两次抵达，196ms

源代码

// by Gospel_rock
#include <vector>
#ifdef LOCAL
#define  _GLIBCXX_DEBUG
#endif 
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front 
#define EM emplace
#define FI first 
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())
#define yyy cout<<"YES\n"
#define nnn cout<<"NO\n"

using namespace std;

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double; 
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;using vii=vector<int>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<DB>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using CD=complex<double>;
static constexpr ll MAXN=(ll)5e3+10,INF=(ll)1e17+3; // 1e17+3??? 1e18+9???
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;

struct Solve{
    vector<bitset<MAXN>> A;          // ???OUT?
    vector<bitset<MAXN>> IN;         // ???IN????????????
    vector<vll> Dis;                 // Dis[u][v] = (???? - 1)???? -1
    bitset<MAXN> ised;               // ????? u ?? BFS ??

    Solve(){
        cin>>N>>Q;
        A.resize(N+5);
        IN.resize(N+5);
        Dis.resize(N+5, vll(N+5, -1));

        // ??????? i ?? j=i+1..N
        FOR(i,1,N){
            FOR(j,1,N-i){
                char a; cin>>a;
                int u=i, v=i+j;
                if(a=='0'){
                    // v -> u
                    A[v].set(u);
                    IN[u].set(v);
                }else{
                    // u -> v
                    A[u].set(v);
                    IN[v].set(u);
                }
            }
        }
        FOR(_,1,Q){
            reply();
        }
    }

    // ?? BFS???????? __ ????=__????? i ??Dis[u][i]=__-1
    void bfs(ll u){
        bitset<MAXN> vis, q; 
        vis.reset(); q.reset();
        q[u]=1; vis[u]=1;

        FOR(__,1,N){
            if(q.none()) break;

            // ???????????
            bitset<MAXN> sum; sum.reset();
            for(int i = q._Find_first(); i <= N; i = q._Find_next(i)){
                sum |= A[i];
            }
            // ????????
            bitset<MAXN> qq = (~vis) & sum;

            // ??????=__?????????? ??-1
            for(int i = qq._Find_first(); i <= N; i = qq._Find_next(i)){
                Dis[u][i] = __ - 1;
            }

            vis |= qq;
            q = qq;
        }
    }

    void reply(){ 
        ll u,v;
        cin>>u>>v;

        // k=0????
        if(A[u][v]){
            cout<<0<<"\n";
            return;
        }

        // k=1???????????? w: u->w && w->v?
        if ( (A[u] & IN[v]).any() ){
            cout<<1<<"\n";
            return;
        }

        // ????
        if(ised[u]){
            cout<<Dis[u][v]<<"\n";
            return;
        }

        // ???? u ???
        ised[u]=true;
        bfs(u);
        cout<<Dis[u][v]<<"\n";
    }
};

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    // cin>>lT;
    // while(lT--)
    Solve a;
    return 0;
}
/*

*/

不判断两次抵达，1309ms

https://qoj.ac/submission/1410868

源代码

// by Gospel_rock
#include <vector>
#ifdef LOCAL
#define  _GLIBCXX_DEBUG
#endif 
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front 
#define EM emplace
#define FI first 
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())
#define yyy cout<<"YES\n"
#define nnn cout<<"NO\n"

using namespace std;

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double; 
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;using vii=vector<int>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<DB>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using CD=complex<double>;
static constexpr ll MAXN=(ll)5e3+10,INF=(ll)1e17+3; // 1e17+3??? 1e18+9???
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;

struct Solve{
    vector<bitset<MAXN>> A;          // ???OUT?
    vector<bitset<MAXN>> IN;         // ???IN????????????
    vector<vll> Dis;                 // Dis[u][v] = (???? - 1)???? -1
    bitset<MAXN> ised;               // ????? u ?? BFS ??

    Solve(){
        cin>>N>>Q;
        A.resize(N+5);
        IN.resize(N+5);
        Dis.resize(N+5, vll(N+5, -1));

        // ??????? i ?? j=i+1..N
        FOR(i,1,N){
            FOR(j,1,N-i){
                char a; cin>>a;
                int u=i, v=i+j;
                if(a=='0'){
                    // v -> u
                    A[v].set(u);
                    IN[u].set(v);
                }else{
                    // u -> v
                    A[u].set(v);
                    IN[v].set(u);
                }
            }
        }
        FOR(_,1,Q){
            reply();
        }
    }

    // ?? BFS???????? __ ????=__????? i ??Dis[u][i]=__-1
    void bfs(ll u){
        bitset<MAXN> vis, q; 
        vis.reset(); q.reset();
        q[u]=1; vis[u]=1;

        FOR(__,1,N){
            if(q.none()) break;

            // ???????????
            bitset<MAXN> sum; sum.reset();
            for(int i = q._Find_first(); i <= N; i = q._Find_next(i)){
                sum |= A[i];
            }
            // ????????
            bitset<MAXN> qq = (~vis) & sum;

            // ??????=__?????????? ??-1
            for(int i = qq._Find_first(); i <= N; i = qq._Find_next(i)){
                Dis[u][i] = __ - 1;
            }

            vis |= qq;
            q = qq;
        }
    }

    void reply(){ 
        ll u,v;
        cin>>u>>v;

        // k=0????
        if(A[u][v]){
            cout<<0<<"\n";
            return;
        }

        // k=1???????????? w: u->w && w->v?
        if ( (A[u] & IN[v]).any() ){
            cout<<1<<"\n";
            return;
        }

        // ????
        if(ised[u]){
            cout<<Dis[u][v]<<"\n";
            return;
        }

        // ???? u ???
        ised[u]=true;
        bfs(u);
        cout<<Dis[u][v]<<"\n";
    }
};

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    // cin>>lT;
    // while(lT--)
    Solve a;
    return 0;
}
/*

*/

心路历程（WA，TLE，MLE……）

START205——Water Supply

Posted on 2025-09-25 Edited on 2026-04-06

思路讲解

单条边的传输关系是单调的
对一条漏水系数为 w 的边，从上游输入 x，到下游得到 x - ⌊x/w⌋；这是关于 x 的非减函数。
因而“想让下游至少得到 need”的逆运算也是单调：最小的上游输入 x 满足 x - ⌊x/w⌋ ≥ need。你代码里的 get(need, w) 就是在做这件事（通过二分求最小可行 x）。
一次修边只能选择一条路径上的一条边
每天只走“根→某个节点”的一条简单路径，因此修哪条边只会影响包含该边的那些路径。
若我们要求所有**“弱点”节点**（即 R[u] < 目标值 mid 的节点）都至少收到 mid，那么被修的那条边必须同时位于它们各自的从根到该点路径上。
这些路径的公共部分正是 根→(所有弱点的 LCA) 的路径。所以：

必要条件：可行的被修边一定在 root → anc 这条路径上，其中 anc 是所有 R[u]<mid 的节点的 LCA。

把“树下游的要求”折算为“对 anc 入水量的要求”
如果我们暂时不修边，问：“从 anc 向下，把整棵以 anc 为根的子树都喂到 ≥ mid，需要 anc 处至少有多少输入？”
由于每条边的传输是单调的，这个“所需的 anc 输入量”是单调的，可以二分出最小可行值 need_at_anc。
你用 dfs2(anc, candidate, mid) 来判定“给 anc 值为 candidate 时，子树是否都 ≥ mid”，并对 candidate 二分拿到最小的 need_at_anc。这一步只会遍历 anc 的子树，而不是整棵树，所以可控。
把 anc 的需求一路往上折算，看是否能借“修一条边”满足
假设我们已经知道：只要 anc 处能拿到至少 need_at_anc 的输入，它子树就都 OK。
现在看 root → anc 这条路径。我们在这条路径上自下而上地把需求往上游推：

当前在节点 node 处需要 need；让 fa=node 的父亲，边权 w=A[node]。
若修边选在 (fa,node) 上，则 node 能直接拿到 R[fa]（因为这条边不再漏水）。于是只要 R[fa] ≥ need 就已经满足了——这就是你代码里的“只要某一层祖先的 R[ancestor] ≥ need****，我们就能在这个祖先与其子之间修边，一步到位”的判定。
否则，如果暂时不修这条边，就要通过这条漏水边把 need 推到父亲处，父亲的所需输入变为 get(need, w)。继续往上迭代，直到找到某个祖先 y 满足 R[y] ≥ 当前 need，那么在 (y, its child) 修边即可；若最终到根也没有成功，则该 mid 不可行。

这正是你 check(mid) 的核心：

先找弱点集合 wp = { i | R[i] < mid }，若空则已可行。
把 anc = LCA(wp 所有点)。
对 anc 的所需输入二分最小可行 need_at_anc（用 dfs2 验证）。
把 need_at_anc 沿 anc→root 方向往上折算：
- 若某处祖先的原始 R[ancestor] ≥ 当前 need → 可在它与子之间修边，成功；
- 否则用 get(need, w) 把需求继续往上推；
- 推到顶都不行则失败。

于是，一次修边能否让所有点 ≥ mid 被转换为上述流程的一个布尔判断。

AC代码

https://www.codechef.com/viewsolution/1194966856

源代码

// by Gospel_rock
#include <bits/stdc++.h>
#include <vector>
#define all(vec) vec.begin(), vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o << 1)
#define rson(o) (o << 1 | 1)
#define SZ(a) ((long long)a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var << ":" << var << "\n";
#define cend cerr << "\n-----------\n"
#define fsp(x) fixed << setprecision(x)
#define minn(vec) *min_element(vec.begin(), vec.end())
#define maxx(vec) *max_element(vec.begin(), vec.end())
#define yyy cout << "YES\n"
#define nnn cout << "NO\n"

using namespace std;

#ifdef LOCAL
template <typename T> void _print(T x) { cerr << x; }
// 可以打印多层数组，但是格式不是很好
template <typename T> void _print(vector<T> v) {
    cerr << "[ ";
    for (T i : v)
        _print(i), cerr << " ";
    cerr << "]";
}
template <typename T> void _print(set<T> s) {
    cerr << "{ ";
    for (T i : s)
        _print(i), cerr << " ";
    cerr << "}";
}
template <typename T, typename U> void _print(pair<T, U> p) {
    cerr << "{";
    _print(p.first);
    cerr << ", ";
    _print(p.second);
    cerr << "}";
}
template <typename T, typename U> void _print(map<T, U> m) {
    cerr << "{ ";
    for (auto &p : m)
        _print(p), cerr << " ";
    cerr << "}";
}
// 打印两层数组，格式好一些
template <typename T> void _print(vector<vector<T>> v) {
    cerr << "{\n";
    for (auto i : v)
        _print(i), cerr << "\n";
    cerr << " }";
}
#endif

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using pdd = pair<DB, DB>;
using plb = pair<ll, bool>;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using vb = vector<bool>;
using tll = tuple<ll, ll, ll>;
using vii = vector<int>;
using vpll = vector<pll>;
using vtll = vector<tll>;
using vdb = vector<DB>;
using vc = vector<char>;
using arr3 = array<ll, 3>;
using arr2 = array<ll, 2>;
using CD = complex<double>;
static constexpr ll MAXN = (ll)2e5 + 10,
                    INF = (ll)1e17 + 3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod = (ll)1e9 + 7;  // 998244353;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll N, M, Q, X, K, T, lT;

struct Solve {
    vector<vector<arr2>> g;
    vector<arr2> edge;
    vll R;
    vll Dep;
    ll op(ll a, ll b) {
        if (Dep[a] <= Dep[b]) {
            return a;
        }
        return b;
    }
    vll fa;
    Solve() {
        cin >> N >> K;
        g.resize(N + 5);
        edge.resize(N + 5);
        Dep.resize(N + 5);
        in.resize(N + 5);
        fa.resize(N + 5);
        R.resize(N+5);
        fa[1]=1;
        FOR(i, 2, N) {
            cin >> edge[i][0];
            fa[i] = edge[i][0];
        }
        FOR(i, 2, N) { cin >> edge[i][1]; }
        FOR(i, 2, N) {
            auto [p, w] = edge[i];
            g[p].PB({i, w});
            g[i].PB({p,w});
        }
        dfs(1, K,1);
        st.resize(__lg(SZ(eu)) + 5, vll(SZ(eu) + 5));
        FOR(i, 0, SZ(eu) - 1) { st[0][i] = eu[i]; }
        FOR(i, 1, __lg(SZ(eu))) {
            FOR(j, 0, SZ(eu) - (1 << i) + 1 - 1) {
                st[i][j] = op(st[i - 1][j], st[i - 1][j + (1ll << (i - 1))]);
            }
        }
        ll mn = INF;
        FOR(i, 1, N) { mn = min(mn, R[i]); }
        ll l = mn, r = K;
        while (l < r) {
            ll mid = l + r + 1 >> 1;
            if (check(mid)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        cout << l << "\n";
    }

    bool check(ll mid) {
        vll wp;
        FOR(i, 1, N) {
            if (R[i] < mid) {
                wp.PB(i);
            }
        }
        if(wp.empty()) return true;
        ll anc = wp[0];
        FOR(i, 1, SZ(wp) - 1) { anc = query(anc, wp[i]); }
        ll l = R[anc], r = K;
        ll check;
        while (l < r) {
            ll mid2 = l + r >> 1;
            if (check2(anc, mid2, mid)) {
                r = mid2;
            } else {
                l = mid2 + 1;
            }
        }
        if (l == K) {
            if (!check2(anc, l, mid)) {
                return false;
            }
        }
        ll node = anc, need = l;
        if (R[anc] >= need)
            return true;
        while (node != 1) {
            if (R[fa[node]] >= need) {
                return true;
            }
            ll w = edge[node][1];
            need = get(need, w);
            if (need == -1)
                return false;
            node = fa[node];
        }
        return false;
    }
    ll get(ll need, ll w) {
        ll l = 0, r = K;
        while (l < r) {
            ll mid = l + r >> 1;
            if (mid - mid / w >= need) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        if (l - l / w < need)
            return -1;
        return l;
    }
    int dfs2(ll u, ll wat, ll lim,ll pa) {
        ll dfs;
        if (wat < lim) {
            return 0;
        }
        int ret = 1;
        for (auto [v, w] : g[u]) {
            if(v==pa) continue;;
            ret &= dfs2(v, wat - wat / w, lim,u);
            if (ret == 0)
                return ret;
        }
        return ret;
    }
    bool check2(ll anc, ll mid, ll lim) { return dfs2(anc, mid, lim,fa[anc]); }
    ll query(ll u, ll v) {
        ll l = in[u], r = in[v];
        if (l > r)
            swap(l, r);
        ll k = __lg(r - l + 1);
        ll res = op(st[k][l], st[k][r - (1ll << k) + 1]);
        return res;
    }
    vll in;
    ll tot = 0;
    vll eu;
    vector<vll> st;
    void dfs(ll u, ll wat,ll pa) {
        R[u] = wat;
        in[u] = tot;
        ++tot;
        eu.PB(u);
        for (auto [v, w] : g[u]) {
            if(v==pa) continue;
            Dep[v] = Dep[u] + 1;
            dfs(v, wat - wat / w,u);
            ++tot;
            eu.PB(u);
        }
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> lT;
    while (lT--)
        Solve a;
    return 0;
}
/*
AC
https://www.codechef.com/viewsolution/1194966856

*/

心路历程（WA，TLE，MLE……）

The 2024 ICPC Asia Nanjing Regional Contest (The 3rd Universal Cup. Stage 16 Nanjing)——F. Subway

Posted on 2025-09-23 Edited on 2026-04-06

思路讲解

AC代码

源代码