Skip to content
TheChatArchiveThe Chat Archive
DeepSeekDeepseek v3.2· deepseekHugging Face Frontier Reasoning Traces

You are given a functional graph. It is a directed graph, in which from each vertex goes…

  1. User

    You are given a functional graph. It is a directed graph, in which from each vertex goes exactly one arc. The vertices are numerated from 0 to n - 1.

    Graph is given as the array f0, f1, ..., fn - 1, where fi — the number of vertex to which goes the only arc from the vertex i. Besides you are given array with weights of the arcs w0, w1, ..., wn - 1, where wi — the arc weight from i to fi.

    The graph from the first sample test.

    Also you are given the integer k (the length of the path) and you need to find for each vertex two numbers si and mi, where:

    • si — the sum of the weights of all arcs of the path with length equals to k which starts from the vertex i;
    • mi — the minimal weight from all arcs on the path with length k which starts from the vertex i.

    The length of the path is the number of arcs on this path. Input

    The first line contains two integers n, k (1 ≤ n ≤ 105, 1 ≤ k ≤ 1010). The second line contains the sequence f0, f1, ..., fn - 1 (0 ≤ fi < n) and the third — the sequence w0, w1, ..., wn - 1 (0 ≤ wi ≤ 108).

    Output

    Print n lines, the pair of integers si, mi in each line.

    Examples

    Input

    7 3 1 2 3 4 3 2 6 6 3 1 4 2 2 3

    Output

    10 1 8 1 7 1 10 2 8 2 7 1 9 3

    Input

    4 4 0 1 2 3 0 1 2 3

    Output

    0 0 4 1 8 2 12 3

    Input

    5 3 1 2 3 4 0 4 1 2 14 3

    Output

    7 1 17 1 19 2 21 3 8 1

  2. DeepSeek Assistant

    We need to solve a problem: given a functional graph (each node has exactly one outgoing edge), with n up to 1e5, and a query k up to 1e10. For each node i, we need to compute sum of weights along the path of length k starting from i (i.e., follow the edges k steps), and the minimum weight among those edges. If we consider the path vertices: i -> f(i) -> f(f(i)) -> ... (k steps). Actually we have arcs from i to f(i) with weight w_i. The sum should be sum of weights of arcs traversed. So if we have path: i0=i, i1=f(i0), i2=f(i1), ..., ik = f(ik-1). The arcs are from i_j to i_{j+1} with weight w_{i_j}. So sum = sum_{j=0}^{k-1} w_{i_j}. min = min_{j=0}^{k-1} w_{i_j}.

    We need to output for each starting node.

    Because k can be huge (1e10), we need to use binary lifting (doubling) technique. Since the graph is functional (each node has exactly one outgoing edge), we can preprocess sparse tables for jumps of powers of two.

    Specifically, define for each node i, after 2^t steps, we know:

    • the node we end up at: nxt[i][t] (like binary lifting ancestor)
    • the total sum of weights along those 2^t steps: sum[i][t]
    • the minimum weight along those steps: min[i][t]

    We can compute these for t = 0 to max_log (max_log such that 2^max_log <= k). Since k up to 1e10, max_log about 34 (2^34 ≈ 1.7e10). So ~35. So we can store arrays of size n * 35 = 3.5e6, which is fine.

    Then for each i, we can decompose k into binary bits, and walk from i, accumulating sum and min (using min over segments). However careful: when we combine two segments a (first L steps) and b (next R steps), we need to combine sums: sum_total = sum_a + sum_b. For minimum: min_total = min(min_a, min_b). However order doesn't matter as min is associative. So we can combine as we jump.

    But note that the path is of length k exactly. So we iterate bits from 0 to max_log, if the bit is set, we take the jump from current node using precomputed values, and then move current node to nxt[current][t] after applying that jump, and accumulate sum and min accordingly.

    Implementation:

    Let MAX_LOG = 34 (since 2^34 > 1e10? 2^34 = 17179869184 > 1e10). Actually 2^33 = 8589934592 < 1e10? 1e10 = 10,000,000,000, so 2^33 ~ 8.6e9 < 1e10, 2^34 ~ 1.7e10 > 1e10. So we need up to 34 (0-indexed). So we can set LOG = 35 (or 35 entries: t=0..34). Let's compute: 2^34 ~ 1.7e10, sufficient. So we need to precompute up to floor(log2(k)) maybe 34 inclusive.

    Thus define up = 35.

    Initialize:

    for i in range(n): nxt[i][0] = f[i] sum[i][0] = w[i] min[i][0] = w[i]

    Then for t from 1 to LOG-1: nxt[i][t] = nxt[ nxt[i][t-1] ][t-1] sum[i][t] = sum[i][t-1] + sum[ nxt[i][t-1] ][t-1] min[i][t] = min( min[i][t-1], min[ nxt[i][t-1] ][t-1] )

    But careful: nxt[i][t-1] might be same as something; works.

    Then for each i:

    node = i total_sum = 0 total_min = INF (like large) remaining = k for t from 0 to LOG-1: if (k >> t) & 1: total_sum += sum[node][t] total_min = min(total_min, min[node][t]) node = nxt[node][t]

    But wait: The ordering of min: Since we are taking the min across all traversed edges, and we are adding jumps in order, we need to combine min correctly. As we start from node i, we jump 2^t steps from the current node. At that point, the path segment includes edges from current node to the node after 2^t steps. Since we then move node forward, the order is preserved. So we can simply update total_min = min(total_min, min[node][t]). That's correct.

    Alternatively, we could process bits from LSB to MSB (or MSB to LSB) as long as we follow order. Since min is associative and commutative, order doesn't matter. So fine.

    After processing all bits, output total_sum and total_min.

    Complexities: O(n log k) time and memory.

    Potential pitfalls: k up to 1e10 fits in 64-bit integer (long long). Use long long for sums (sums could be up to k * max w = 1e10 * 1e8 = 1e18, which fits in 64-bit? 1e18 < 2^63-1 ~ 9.22e18, so safe. Actually 1e10*1e8 = 1e18 exactly, so within 64-bit signed: max 9.22e18, so safe). However if n=1e5 and each w=1e8, and k=1e10, sum = 1e18. So use long long (int64_t). For min, w up to 1e8, so int is fine.

    We need to store arrays: nxt[LOG][n]? Or [n][LOG]. Usually we do [n][LOG] for cache? But either works. Since n up to 1e5 and LOG=35, we can do:

    vector<vector> nxt(LOG, vector(n)); vector<vector> sum(LOG, vector(n)); vector<vector> mn(LOG, vector(n));

    But better to allocate as [n][LOG]? Let's think: we will often iterate over i and then over t, so [n][LOG] may be more cache-friendly. However both are fine for 1e5*35=3.5 million ints. For sum it's 3.5 million long longs (28 MB). For mn it's 3.5 million ints (14 MB). For nxt it's 3.5 million ints (14 MB). Total ~56 MB, okay.

    We need to watch out: We need to compute nxt[ nxt[i][t-1] ][t-1]. If we store as [i][t], accessing nxt[some][t-1] is fine.

    Implementation details:

    • Read n, k (k is long long).
    • Read arrays f (size n) and w (size n).
    • Determine LOG: While (1LL << LOG) <= k, maybe LOG = 60? But we can fix to 35 because k <= 1e10, but to be safe maybe compute: int LOG = 0; while ((1LL << LOG) <= k) LOG++; (or while ((1LL << LOG) <= k) LOG++). Then we need from 0 to LOG-1 inclusive. Actually we need powers up to the highest bit set; but we also need to cover case where k=0? But k>=1, so fine. However we might need to compute up to 60 if we want generic? But since constraints say k ≤ 1e10, 35 enough. But we can compute dynamic: LOG = floor(log2(k)) + 1. Use while loop. But careful: For building the table, we need to compute up to LOG-1 anyway. Actually for binary lifting we often precompute up to maximum log needed, which is up to about 60 for 64-bit. But with n=1e5 and LOG=60, memory would be 6 million per array, maybe still okay? 601e5 = 6 million; long long sum: 6M8=48MB; int nxt: 6M*4=24MB; int mn: 24MB; total ~96MB, might be borderline but still okay? However typical memory limit might be 256 MB, so fine. But we can just compute dynamic: we can precompute up to 60 to be safe for any k up to 1e18, but the problem's k is only up to 1e10, so 35 is enough. I'll compute max_log = 60 just to be generic? Actually I'm not sure about time: building 60 steps * n = 6 million operations, fine. But memory: 60 * 1e5 = 6e6, * 8 for sum = 48MB, plus nxt (4 bytes) 24MB, mn (4 bytes) 24MB, total 96MB. Might be okay if memory limit is 256MB. But I'd rather keep it at minimal to be safe. However, I need to be careful: some judges may have memory limit 64 MB? Usually Codeforces problems have 256 MB. Let's check: Problem is from Codeforces? Possibly 256 MB. So 96 MB is okay. But I'd compute the exact required LOG based on k. Since k can be up to 1e10, we can compute:

    int max_log = 0; while ((1LL << max_log) <= k) max_log++; // but we need up to max_log-1 for table; but we also need to compute one extra? Actually we need to jump for each bit set. If we have the highest bit, say k=8 (2^3), we need table up to t=3 (2^3). So we need t such that 2^t <= k. So we can compute LOG = floor(log2(k)) + 1 (number of bits). For t=0..LOG-1, 2^t <= k. So we need table up to LOG-1. For building, we need to compute from t=1 to LOG-1 inclusive. So we can set LOG = 0; while ((1LL << LOG) <= k) LOG++; Then the maximum t needed is LOG-1. But we need to be able to access up to LOG-1. So we can allocate LOG as that number. But careful: For t=LOG-1, we have 2^(LOG-1) <= k. For building, we need to compute values for t=1..LOG-1. So it's fine. However, we might need to use table for jumps that are exactly the bit positions when we decompose k. Since we will only use bits where (k>>t) &1. So we need all t up to floor(log2(k)). So allocate LOG = floor(log2(k)) + 1.

    Simplify: we can set a constant MAX_LOG = 40 (since 2^40 ~ 1e12 > 1e10). Or 45 to be safe for 1e18? I'd set MAX_LOG = 60, but that uses more memory. To be safe, we can allocate vector<vector<...>> with LOG = 40. That's 40 * 1e5 = 4e6, sum 32 MB, nxt 16 MB, mn 16 MB total 64 MB, okay. So I'll set MAX_LOG = 40.

    But we need to compute up to log2(1e10) ~ 34, so 40 is safe.

    Implementation: #define LOG 40.

    But careful: For n=1e5, we precompute table of size LOG * n. That's fine.

    Alternatively, we could compute LOG based on 64 - __builtin_clzll(k) but that's fine.

    Let's implement.

    Potential issues: For min, we need to combine correctly. Since min of two segments is just the min of both. However, careful: The path's edges order is sequential; but min is associative, so combining in any order yields the same. So we can combine as we go.

    Also note: The graph is functional, but there might be cycles. This method works irrespective of cycles because binary lifting just computes the destination after many steps, sum and min correctly.

    Edge cases: k=1 -> only one edge. Should work.

    Now, let's test with given examples.

    Example 1:

    n=7, k=3 f: [1,2,3,4,3,2,6] w: [6,3,1,4,2,2,3]

    Let's compute manually for node 0:

    Path: 0->1 (w6), 1->2 (w3), 2->3 (w1). Sum = 6+3+1=10, min=1. Output 10 1.

    Node 1: 1->2 (3), 2->3 (1), 3->4 (4) -> sum=3+1+4=8, min=1 -> matches.

    Node 2: 2->3 (1), 3->4 (4), 4->3 (2) -> sum=1+4+2=7, min=1 -> matches.

    Node 3: 3->4 (4), 4->3 (2), 3->4 (4) -> sum=4+2+4=10, min=2? Actually min among [4,2,4] is 2 -> matches.

    Node 4: 4->3 (2), 3->4 (4), 4->3 (2) -> sum=2+4+2=8, min=2 -> matches.

    Node 5: 5->2 (2), 2->3 (1), 3->4 (4) -> sum=2+1+4=7, min=1 -> matches.

    Node 6: 6->6? Actually f[6]=6? No f[6]=6? Given f: "1 2 3 4 3 2 6" -> f[6]=6 (self-loop?). w[6]=3. Path: 6->6 (3), 6->6 (3), 6->6 (3) -> sum=9, min=3 -> matches. So it works.

    Example 2:

    n=4, k=4, f: 0,1,2,3 (each points to itself?) Actually f: 0 1 2 3, so each points to itself? 0->0, 1->1, 2->2, 3->3. w: 0,1,2,3. So from i, path: 4 steps of self-loop. Sum = 4 * w_i, min = w_i. Output as given: 0,0; 4,1; 8,2;12,3.

    Example 3:

    n=5, k=3 f: [1,2,3,4,0] w: [4,1,2,14,3]

    Let's compute node 0: 0->1 (4), 1->2 (1), 2->3 (2) -> sum=7, min=1 -> matches output: 7 1.

    Node 1: 1->2 (1), 2->3 (2), 3->4 (14) -> sum=1+2+14=17, min=1 -> matches.

    Node 2: 2->3 (2), 3->4 (14), 4->0 (3) -> sum=2+14+3=19, min=2? Actually min=2? Output says 19 2 -> matches.

    Node 3: 3->4 (14), 4->0 (3), 0->1 (4) -> sum=14+3+4=21, min=3? Output says 21 3 -> matches.

    Node 4: 4->0 (3), 0->1 (4), 1->2 (1) -> sum=3+4+1=8, min=1 -> matches.

    Thus method works.

    Now implement.

    Pseudo-code:

    #include <bits/stdc++.h> using namespace std;

    typedef long long ll; const int MAXN = 100000; const int LOG = 40; // enough for 1e12

    int main() { int n; ll k; cin >> n >> k; vector f(n), w(n); for (int i = 0; i < n; ++i) cin >> f[i]; for (int i = 0; i < n; ++i) cin >> w[i];

    // precompute binary lifting tables
    int LOG = 0;
    while ((1LL << LOG) <= k) LOG++; // we need up to LOG-1 inclusive
    // but we might need to allocate LOG+1? Actually we need indices 0..LOG-1. So allocate LOG.
    vector<vector<int>> nxt(LOG, vector<int>(n));
    vector<vector<ll>> sum(LOG, vector<ll>(n));
    vector<vector<int>> mn(LOG, vector<int>(n));
    
    // base
    for (int i = 0; i < n; ++i) {
        nxt[0][i] = f[i];
        sum[0][i] = w[i];
        mn[0][i] = w[i];
    }
    
    // build
    for (int t = 1; t < LOG; ++t) {
        for (int i = 0; i < n; ++i) {
            int mid = nxt[t-1][i];
            nxt[t][i] = nxt[t-1][mid];
            sum[t][i] = sum[t-1][i] + sum[t-1][mid];
            mn[t][i] = min(mn[t-1][i], mn[t-1][mid]);
        }
    }
    
    // answer queries
    for (int i = 0; i < n; ++i) {
        int node = i;
        ll total_sum = 0;
        int total_min = INT_MAX; // but w up to 1e8, so maybe 1e9.
        ll remaining = k;
        for (int t = 0; t < LOG; ++t) {
            if (k & (1LL << t)) {
                total_sum += sum[t][node];
                total_min = min(total_min, mn[t][node]);
                node = nxt[t][node];
            }
        }
        cout << total_sum << " " << total_min << "\n";
    }
    
    return 0;
    

    }

    But we need to be careful: When we do the combination, we used variable 'node' that gets updated. Since we are iterating t from 0 upward, it corresponds to processing bits from LSB to MSB. That is correct because the jumps are applied in order: first 2^0, then 2^1, etc. However, we must ensure that the precomputed sum[t][node] and mn[t][node] correspond to the path starting from the current node after previous jumps? But we are updating node after each jump, so the next jump uses the new node. That's correct. But note that when we process bits, the order we apply jumps matters: If we process from LSB to MSB, we are essentially taking smaller jumps first, then larger ones, which is still correct because the path is sequential. The composition of sums and mins is associative, so order is irrelevant, but the destination node must be updated accordingly. For destination, the order matters: if we jump 2^0 then 2^2 then 2^5, the total is the same as if we jumped 2^0, then from there 2^2, etc. That's exactly what we do: we start at node i, apply the smallest jump first (if bit set), node becomes nxt[0][i]; then if next bit is set, we apply from that node using precomputed jump for 2^1, etc. So this yields the correct final node.

    Alternatively, we could process from MSB to LSB. But the current approach is fine.

    Potential overflow: sum[t][i] can be up to 1e18, and we accumulate total_sum possibly up to 1e18, within long long.

    We need to initialize total_min to something large like 1e9+1 or INT_MAX? w[i] up to 1e8, so we can set total_min = 2e9. But we could also use a large constant like 1e9+7. Since we will take min with actual w values (all <= 1e8). So 2e9 is safe. Or use 1<<30 etc. But better use numeric_limits::max().

    Now about LOG: The precomputation uses LOG = floor(log2(k)) + 1. However, we might have case where k=0? But problem says k>=1, so fine. But we also need to consider that we precompute for t up to LOG-1. But we need to be able to access bits up to highest set bit. Suppose k=1e10, then LOG computed by while loop: (1LL<<LOG) <= k. Initially, LOG=0: 1 <= k => true; ... up to 2^34=17179869184 > 1e10, so the while condition stops when (1LL << LOG) <= k becomes false. At that point LOG is the smallest integer such that 2^LOG > k. For k=1e10, floor(log2(k)) = 33? Actually 2^33 = 8589934592, 2^34=17179869184. So floor(log2(1e10)) = 33, because 2^33 = 8.59e9 < 1e10, 2^34 > 1e10. So the smallest integer with 2^LOG > k is 34, so LOG = 34. But we need to have entries for t=0..33 (since 2^33 <= k). So if we allocate LOG = 34, that gives indices 0..33, which is floor(log2(k)). But we need index 33 because 2^33 <= k. However, note that we also need to check bits: bits from 0 to floor(log2(k)) inclusive? Actually for k=8 (1000 binary), bits are positions 0,1,2,3? Wait, bit positions: 8 = 1000 binary, so the bits are at position 3 (value 8). floor(log2(8)) = 3, so we need t=3. So we need indices up to floor(log2(k)). With LOG = floor(log2(k)) + 1. So for k=8, floor(log2(8))=3, +1 =4, so allocate indices 0..3. That works. For k=1e10, floor(log2(1e10)) = 33, so allocate indices 0..33. But our while loop gave LOG = 34, which is floor(log2(k)) + 1? Let's compute: floor(log2(1e10)) = 33 (since 2^33 ~ 8.59e9, 2^34 ~ 1.72e10). So floor+1 = 34. So LOG = 34 indeed. So we have indices 0..33. That's correct. So the while condition should be: while ((1LL << LOG) <= k) LOG++; This yields LOG = number of bits such that 2^(LOG-1) <= k and 2^LOG > k? Actually if we start LOG=0, we increment while <=. After loop, LOG is the smallest such that 2^LOG > k. So it's floor(log2(k)) + 1. That's what we want.

    But if we allocate vector(n) with LOG as this computed value, we have indices 0..LOG-1, that's floor(log2(k)). Good.

    Now we need to ensure that we compute the table for t from 1 to LOG-1 inclusive.

    Edge: If k is 0 (not allowed) we would have LOG=0, then no table, but we don't need.

    Now potential issue: When we later loop t from 0 to LOG-1 and check (k>>t) & 1, we need t up to LOG-1 inclusive. That's fine. Since LOG is the number of bits needed to represent k (i.e., floor(log2(k)) + 1), the highest bit set is at most LOG-1. So checking bits up to LOG-1 covers all bits.

    Now what about when we compute nxt[t][mid] where t-1 might be up to LOG-1? It's fine.

    Now let's test with small example: n=1, k=1. f[0]=0, w[0]=something. LOG: while(1<<0 =1 <=1) LOG=1; then while(1<<1=2 <=1?) false, so LOG=1. Then we allocate nxt[1][1]? Actually LOG=1, so we have indices 0 only. Build base: t=0. Then for t=1 to <1? none. Then for each i, loop t=0 to <1 (only t=0). Check bit 0 of k: k=1 => bit0 set. total_sum = sum[0][node] = w[0]; total_min = w[0]; node = nxt[0][node] = f[0]; output. Good.

    Now test with k=2 (binary 10). floor(log2(2))=1, so LOG=2 (indices 0..1). Build base t=0. Then t=1: we compute using nxt[0][...]. Then for i, loop t=0,1. Bits: t=0 not set, t=1 set. So we use sum[1][i] which is sum of 2 steps. That's correct.

    So algorithm is correct.

    Now we must consider memory usage. We allocate vector of vectors: each inner vector of size n, outer of size LOG. That's fine.

    But we can also compress by using arrays of size [LOG][n] but with vectors.

    Implementation details in C++: Use long long for k and sums.

    Also note that sum[t][i] may be large, but we add many of them: total_sum may exceed 2^63? Max sum is k * max w = 1e10 * 1e8 = 1e18. 2^63-1 is 9.22e18, so safe.

    Now potential bug: In precomputation, we have to ensure that we access nxt[t-1][mid] where mid could be any node up to n-1. That's fine.

    Now test with larger n and random.

    One more nuance: When we combine min, we must be careful about int overflow? min is int, fine.

    Now, can there be any pitfalls with large recursion? No.

    Time: O(n log k) ≈ 1e5 * 35 = 3.5e6, plus building table O(n log k) as well. Fine.

    Now, alternative method: Use cycle detection and handle queries for k large by reducing modulo cycle length etc. But binary lifting is simpler.

    Now confirm for Example 1 with our method.

    We'll simulate maybe manually for node 0:

    k=3 (binary 11). LOG = while(1<<0=1 <=3) LOG=1; while(1<<1=2<=3) LOG=2; while(1<<2=4<=3) false => LOG=2? Actually 2^2=4 >3, so loop stops at LOG=2? Wait step: start LOG=0, while((1LL<<0)=1<=3) LOG=1; now LOG=1, check (1<<1)=2 <=3 -> true, so LOG=2; now LOG=2, check (1<<2)=4 <=3 false, exit. So LOG=2. But 3 needs bits 0 and 1. So we need t=0 and t=1. That's fine. With LOG=2, we have indices 0 and 1. But we also need to jump for t=1? Yes, we have sum[1][i] which is sum of 2 steps. Then we apply t=0 then t=1? Actually if we process t=0 first (LSB) we take 1 step, then t=1 (2 steps) from the new node, total 3 steps. That's correct. However, we need to also have precomputed for t=1. So we need to compute up to t=1. With LOG=2, we have t=0,1. Good. But wait, is t=1 enough for k=3? Yes. But what about a node that needs to jump 2 steps from the initial? That is covered.

    But consider k=4 (binary 100). floor(log2(4))=2, so LOG=3 (indices 0..2). So we need t=2. So the formula works.

    Thus our LOG must be at least floor(log2(k))+1.

    But careful: For building table, we need values for t up to floor(log2(k)). So our LOG = floor(log2(k)) + 1 is enough. However, consider if k has highest bit at position H, then we need tables up to H. For k=1e10, H=33, so we need t=33. So LOG=34. But we used constant MAX_LOG = 40 to avoid computing dynamic. But dynamic is also okay.

    Potential issue: When we compute the table for t from 1 to LOG-1, we need that nxt[t-1][mid] is already computed. For t=1, we use nxt[0][...] which is base. For t>1, we need previous. So fine.

    Now about the loops: We might want to use array of vectors; but iterating over t outer loop and i inner loop is okay.

    However, we need to ensure we use correct types: The variable mid may be up to n-1, fine.

    Now, the answer for each node: total_sum and total_min.

    Now, one more nuance: For large k, the path length is exactly k. But if the graph is functional, there is always exactly one outgoing edge per node, so the path is well-defined for any length, even beyond cycles. So no issues.

    Thus solution is straightforward.

    Now, potential performance improvement: Use 2D arrays as vector of vectors is slower but acceptable for 3.5 million entries. But we can also use 1D arrays of size n*LOG and index manually, but not needed.

    Now double-check for correct handling of min: The minimum over empty set is not defined; k>=1 so at least one edge.

    Now test with Example 2: n=4, k=4. floor(log2(4))=2, LOG=3. Build base: t=0; t=1: compute sum[1][i] = sum[0][i] + sum[0][nxt[0][i]]; etc. For node 0: nxt[0][0]=0, so sum[1][0] = w0+w0=0? Actually w0=0, so sum[1][0]=0, min[1][0]=min(0,0)=0; nxt[1][0] = nxt[0][ nxt[0][0] ] = nxt[0][0]=0. t=2: sum[2][0] = sum[1][0] + sum[1][ nxt[1][0] ] = 0+0=0; min[2][0] = min(0,0)=0; nxt[2][0] = nxt[1][ nxt[1][0] ] =0.

    Now k=4 = binary 100 (bits: t=2 set, t=0 and t=1 not). So for i=0, we use t=2: total_sum = sum[2][0]=0, total_min = min[2][0]=0, node = nxt[2][0]=0. Output (0,0) correct. For i=1: w1=1, base: nxt[0][1]=1, sum[0][1]=1, min[0][1]=1. t=1: nxt[1][1] = nxt[0][ nxt[0][1] ] = nxt[0][1]=1; sum[1][1] = sum[0][1] + sum[0][1] = 2; min[1][1] = min(1,1)=1. t=2: nxt[2][1] = nxt[1][ nxt[1][1] ] = nxt[1][1]=1; sum[2][1] = sum[1][1] + sum[1][1] = 4; min[2][1] = min(1,1)=1. Then answer: t=2 set => sum=4, min=1 -> correct. So method works.

    Now consider if we process bits from LSB to MSB for node 1 with k=4: only t=2 set, we jump 4 steps; correct.

    Now consider k=5 (101) for a node with self-loop weight 1. We need sum=5, min=1. With LOG=3, bits t=0 and t=2 set. Process t=0: jump 1 step, sum=1, min=1, node stays same (self-loop). Then t=2: from that node after 1 step, we jump 4 steps: sum adds 4, min adds 1 (min= min(1,1)=1). total=5, min=1, node final after 5 steps. Works.

    Now about min combination: When we combine two segments (first segment min=1, second min=1), min is 1. All good.

    Thus solution stands.

    Now about potential overflow in sum[t][i] during precomputation: w_i up to 1e8, and sum of up to 2^t edges. For t up to 34, 2^34 ~ 1.7e10, sum up to 1.7e10 * 1e8 = 1.7e18, which fits in 64-bit signed (max ~9.22e18). So safe.

    Now implement in code.

    But we need to be careful about reading input: n up to 1e5, k up to 1e10, so use long long for k. Use int for f and w (since fi and wi within int). But wi up to 1e8 fits in int. fi up to 1e5-1 fits in int.

    Now code.

    We'll define constants: maybe LOG_MAX = 60 to be safe for 10^10? Actually 2^60 ~ 1e18. But we can compute required LOG dynamically to save memory. I'll compute LOG = 0; while ((1LL << LOG) <= k) LOG++; // gives floor(log2(k))+1.

    But careful: If k=0? Not allowed.

    But we must also consider if k is very large e.g., 10^10, then LOG=34, we allocate 34 arrays. That's fine.

    Alternatively, we can set LOG = 61 (to handle up to 10^18) and allocate that many, which might be bigger but still okay. But I'll go dynamic.

    Implementation details: Use vector<vector> for nxt and mn, and vector<vector> for sum. For performance, we might allocate them as vector< vector > nxt(LOG, vector(n)); but then we need to know LOG at runtime, which we can. However, vector of vector has overhead but acceptable.

    Alternatively, we could allocate a 2D array using new, but easier with vectors.

    Potential pitfall: When building the table, we need to ensure that we compute for each t, for each i, nxt[t][i] correctly. Access pattern: For each t, we loop i from 0 to n-1. That is fine.

    Now let's test with k that is not a power of two: e.g., k=3, LOG=2? Actually we got LOG=2 earlier. But we need to be able to jump 2 steps as one jump (t=1). That's enough because we need t=0 and t=1. But what about the jump of size 2? That's t=1. So LOG=2 yields tables for t=0 and t=1. That's sufficient. But we must be careful: When we decompose k=3, we need bits 0 and 1. That's fine.

    Now for k=5, floor(log2(5))=2, so LOG=3, t=0,1,2. Bits: 0 and 2 set. So we need t=2 (size 4) and t=0 (size 1). So we need table up to t=2. So LOG=3 correct.

    Now compute LOG: while ((1LL << LOG) <= k) LOG++; But for k=5, start LOG=0, 1<=5 => LOG=1; 2<=5 => LOG=2; 4<=5 => LOG=3; 8<=5? false, so LOG=3. Good.

    Now building table for t up to LOG-1 = 2, so we compute t=1 and t=2.

    Now final step: For each i, we iterate t from 0 to LOG-1. But we must be careful: When we check (k >> t) & 1, we need to ensure that t does not exceed 63 maybe, but we only go to LOG-1, and LOG is at most 34, so fine.

    Now about the node variable: we update node = nxt[t][node] only when bit set. That's correct.

    Now we output total_sum and total_min.

    Complexities: O((n+Q) log k) but Q=n. So O(n log k).

    Now potential edge: The sum might be large, but we use long long.

    Now consider if k is extremely large (1e10), but we still only need LOG about 34, fine.

    Now let's double-check the initial building step: For t from 1 to LOG-1, we compute for each i:

    mid = nxt[t-1][i]; // node after 2^{t-1} steps from i nxt[t][i] = nxt[t-1][mid]; sum[t][i] = sum[t-1][i] + sum[t-1][mid]; mn[t][i] = min(mn[t-1][i], mn[t-1][mid]);

    This works because the path from i of length 2^t can be split into two halves: first 2^{t-1} steps from i to mid, then next 2^{t-1} steps from mid. The sum and min across the whole segment are combination of the two halves.

    Now, is there any potential issue with min combination? Yes, the min across the whole segment is the min of the two halves, correct.

    Now ensure that mid is within range; it always is.

    Now verify with a case where the path goes into a cycle and then continues; but binary lifting handles it correctly.

    Now note: The problem may have n up to 1e5, so memory usage ~ O(n log k). With LOG=34, n=1e5, each array of ints: 34*1e5 = 3.4e6 ints, each 4 bytes = 13.6 MB per array. For sum (long long) 8 bytes each => 27.2 MB. So total ~13.6+13.6+27.2=54.4 MB. That's acceptable.

    Now we need to produce output in the specified format: each line two integers si and mi. Should be printed as two integers separated by space.

    Now test with given examples using a mental run.

    Now, let's consider an alternative approach: Using exponentiation by squaring on the functional graph. This is essentially binary lifting.

    Now code.

    Potential micro-optimizations: Use arrays of vectors but maybe we can store as vector<vector> with .resize.

    Implementation:

    int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; long long k; cin >> n >> k; vector f(n), w(n); for (int i = 0; i < n; ++i) cin >> f[i]; for (int i = 0; i < n; ++i) cin >> w[i];

    // compute LOG
    int LOG = 0;
    while ((1LL << LOG) <= k) ++LOG;
    // we need tables for t=0..LOG-1
    vector<vector<int>> nxt(LOG, vector<int>(n));
    vector<vector<long long>> sum(LOG, vector<long long>(n));
    vector<vector<int>> mn(LOG, vector<int>(n, 1e9)); // but we will fill anyway
    
    // base t=0
    for (int i = 0; i < n; ++i) {
        nxt[0][i] = f[i];
        sum[0][i] = w[i];
        mn[0][i] = w[i];
    }
    
    // build
    for (int t = 1; t < LOG; ++t) {
        for (int i = 0; i < n; ++i) {
            int prev = nxt[t-1][i];
            nxt[t][i] = nxt[t-1][prev];
            sum[t][i] = sum[t-1][i] + sum[t-1][prev];
            mn[t][i] = min(mn[t-1][i], mn[t-1][prev]);
        }
    }
    
    // answer
    for (int i = 0; i < n; ++i) {
        int node = i;
        long long s = 0;
        int m = 1e9 + 10;
        long long K = k;
        for (int t = 0; t < LOG; ++t) {
            if (K >> t & 1) {
                s += sum[t][node];
                m = min(m, mn[t][node]);
                node = nxt[t][node];
            }
        }
        cout << s << " " << m << "\n";
    }
    
    return 0;
    

    }

    But note: In the base, w[i] can be 0, so min might be zero, that's fine.

    Now what about the case where LOG=0? Not possible because k>=1, so LOG>=1.

    Now, we must be careful that we use 1LL << LOG for comparison, and (K >> t) & 1 uses K as long long; we can also use k directly.

    Now potential bug: When we compute LOG, we do while ((1LL << LOG) <= k) ++LOG; This might cause LOG to be up to 64 if k is huge? But k <= 1e10, so max 34. So fine.

    But note: 1LL << LOG could overflow if LOG>=63, but not here.

    Now check with Example 1:

    n=7, k=3 => LOG computed: while (1<=3) LOG=1; while (2<=3) LOG=2; while (4<=3) false => LOG=2.

    Then we allocate tables for t=0,1. But we need to be able to handle k=3 which has bits 0 and 1 set. But we have t=1 which is 2 steps. That works. But do we need t=2? No.

    But is it enough to cover a jump of 2 steps? Yes. So correct.

    But careful: For node i, if we need to combine 2 steps and 1 step, we need to apply t=1 then t=0? In our loop from t=0 to LOG-1, we apply t=0 first, then t=1. That gives 1 step then from that new node apply 2 steps, total 3. That's correct. But what if we apply t=1 first then t=0? That would be 2 steps then 1 step, total 3, also correct because min is commutative, and the path sum is same (addition is commutative but order of edges is same? Actually the path order matters for sum only in terms of which edges we traverse. If we do 2 steps then 1 step, that yields the same total sum (since addition is commutative) but the actual path visited might be different? Let's test: Starting from i, applying a jump of 2 steps yields i -> f(i) -> f(f(i)). Then applying a jump of 1 step from that node yields f(f(i)) -> f(f(f(i))). So total path: i -> f(i) -> f(f(i)) -> f(f(f(i))). That's exactly the first 3 steps (i -> ...). However, if we apply 1 step first then 2 steps, we get: i -> f(i) -> f(f(i)) -> f(f(f(i))). Same path. So order does not matter because the jumps are powers of two and they are applied sequentially, but the path is determined by the order of jumps: if you jump 2 steps then 1 step, you are effectively taking steps 0-1-2 then step 3? Wait, let's think: Starting at i. After 2 steps, you are at node after 2 steps. If you then take 1 step, you move one further, so total steps = 3. The sequence of nodes visited: first two edges: from i to f(i) to f(f(i)). Then one more: from f(f(i)) to f(f(f(i))). So the total visited edges are exactly the first three edges: i->f(i), f(i)->f(f(i)), f(f(i))->f(f(f(i))). If instead you take 1 step first: i->f(i); then 2 steps from f(i): f(i)->f(f(i))->f(f(f(i))). So visited edges: i->f(i) (first), then f(i)->f(f(i)) (second), then f(f(i))->f(f(f(i))) (third). Same sequence. So order doesn't matter as long as the jumps are applied from the current node appropriately, because jumps are associative: Jump 2 from i then 1 from that node yields same final node as jump 1 from i then 2 from that node? Let's verify: Jump 2 from i gives node = f^2(i). Jump 1 from that gives f^3(i). Jump 1 from i gives f(i). Jump 2 from f(i) gives f^3(i). So both yield same final node. The sum is also same: sum(i,2) + sum(f^2(i),1) = w_i + w_{f(i)} + w_{f^2(i)}. And sum(i,1) + sum(f(i),2) = w_i + (w_{f(i)} + w_{f^2(i)}) = same. So indeed addition is commutative but more importantly it's associative. So both orders give same total sum and min. So iterating from LSB to MSB is fine.

    Now confirm with example where jumps are not commutative? Actually jumps are deterministic, but the composition of jumps of sizes a and b is the same as a+b steps, regardless of order, because the function f is applied repeatedly and the path is deterministic. So indeed, it's just the same as applying steps sequentially. So as long as we combine sums and mins correctly, order doesn't matter. But we do need to be careful about the order for min? min is also commutative. So fine.

    Thus algorithm is correct.

    Now, implement in C++.

    Potential improvement: Instead of storing mn as int, we could store as int but initialize to large value. But we must ensure that min over large k works. Since min across segments is the minimum of all weights along those edges, it's safe.

    Now final code.

    But note: The graph might have self-loops or cycles, but no issue.

    Now we also need to consider the case where k is extremely large and maybe we need to compute up to 60. But as we set LOG dynamically, it's fine.

    However, there is a nuance: In the precomputation, we use nxt[t-1][mid] where mid could be any node. Since nxt[t-1][mid] is defined for all mid. So it's fine.

    Now testing with large values: If k=1e10, LOG=34, table built for t=0..33. That's 34 rows. In the answer loop, we iterate t=0..33, check bits. Good.

    Now, is there any risk of overflow when computing sum[t][i] = sum[t-1][i] + sum[t-1][mid]? This sum could exceed 2^63? But as argued, max sum per entry is at most 2^t * max w. For t=33, 2^33 ~ 8.6e9, max w=1e8 => 8.6e17, plus sum of two such could be up to 1.72e18, still < 9.22e18. So safe.

    Now memory: vector<vector> sum(LOG, vector(n)). For n=1e5, LOG=34, that's 341e58 = 27.2 MB. vector<vector> nxt and mn each: 341e54 = 13.6 MB each, total ~54.4 MB. That's fine.

    Now ensure we use fast I/O: ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    Now we output each line with space and newline.

    Now potential bug: For the min initialization, we set m = something high, but if we never enter the if condition (i.e., k=0) then m would remain large, but k>=1 so at least one bit set. So safe.

    But just in case, we can set m to a large number like 1e9+7.

    Now check with sample input.

    We should test manually with the code mentally for example 1.

    But also note: In the building step, for t=1, we compute mid = nxt[0][i] = f[i]. Then nxt[1][i] = nxt[0][mid] = f[ f[i] ]. sum[1][i] = sum[0][i] + sum[0][mid] = w[i] + w[f[i]]. mn[1][i] = min(w[i], w[f[i]]). That's correct.

    Now for node 0: f[0]=1, f[1]=2. So nxt[1][0] = f[ f[0] ] = f[1]=2. sum[1][0]=6+3=9. mn[1][0]=min(6,3)=3.

    Now for k=3, bits: t=0 (1) and t=1 (2). So we first apply t=0: add sum[0][0]=6, m=min(6)=6, node becomes f[0]=1. Then apply t=1: from node=1, add sum[1][1]? Wait careful: When we process t=1, we are at node=1 after first jump. Then sum[1][1] is sum of two steps from node 1: that is w[1]+w[f[1]] = 3+1=4, min[1][1] = min(3,1)=1. So total sum =6+4=10, total min = min(6,1)=1. Node becomes nxt[1][1]= f[ f[1] ]? Actually nxt[1][1] = f[ f[1] ] = f[2]=3. So final node 3. Output sum=10, min=1. Good.

    If we had processed t=1 first (if we reversed order), we would have: t=1: sum[1][0]=9, m=3, node=2; t=0: sum[0][2]=1, m=min(3,1)=1, node= f[2]=3, total sum=10. Same.

    So order doesn't matter.

    Now example 2: node 1, k=4 bits: only t=2 set. sum[2][1] = w1 + w1 + w1 + w1? Actually from building: t=2 sum = w1*4 =4, min=1. Node stays 1. So output 4,1.

    Now example 3: Let's test node 2, k=3 (011 binary? Actually 3=11 binary, bits 0 and 1). LOG computed: while(1<=3) LOG=1; while(2<=3) LOG=2; while(4<=3) false => LOG=2. So only t=0,1. For node 2: base: nxt[0][2]=f[2]=3, sum=2, min=2. t=1: nxt[1][2] = f[f[2]] = f[3]=4, sum[1][2] = w2 + w3 = 2+14=16, min[1][2] = min(2,14)=2. Now k=3: bits: t=0 and t=1. Process t=0: sum+=2, min=2, node=3. t=1: from node=3, sum[1][3] = w3 + w4 = 14+3=17, min[1][3]=min(14,3)=3, total sum=2+17=19, total min=min(2,3)=2, node= nxt[1][3]= f[f[3]] = f[4]=0. So outputs 19 2. Good.

    Thus works.

    Now, we should also consider the scenario where k is extremely large like 1e10, and we have many nodes, performance is fine.

    Now, potential improvement: We could use 1D arrays and compute on the fly to reduce memory, but not needed.

    Now ensure we handle the case where nxt and sum arrays are accessed with indices that are within range.

    Now note: In the answer loop, we use variable K (maybe long long) but we can use k directly. But we should be careful that we don't modify k, so we use k for bit testing.

    Now about the bit test: if (k & (1LL << t))? But when t is large (like 34), 1LL << t is safe within 64-bit.

    But note: If we use (k >> t) & 1, it's also safe.

    I'll use if (k >> t & 1) or if (k & (1LL << t)). Both work.

    Now code:

    #include #include #include using namespace std;

    int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; long long k; cin >> n >> k; vector f