結果

問題 No.2258 The Jikka Tree
ユーザー lam6er
提出日時 2025-04-09 21:02:55
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,586 bytes
コンパイル時間 2,147 ms
コンパイル使用メモリ 200,032 KB
実行使用メモリ 16,072 KB
最終ジャッジ日時 2025-04-09 21:05:30
合計ジャッジ時間 16,699 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 2 WA * 1 TLE * 1 -- * 71
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

const int LOG = 20;
const int MAXN = 150000;

vector<int> adj[MAXN];
int depth[MAXN];
int up[MAXN][LOG];
int parent[MAXN];

int tin[MAXN], tout[MAXN], timer = 0;

void dfs(int u, int p) {
    parent[u] = p;
    tin[u] = timer++;
    up[u][0] = p;
    for (int j = 1; j < LOG; j++)
        up[u][j] = up[up[u][j-1]][j-1];
    for (int v : adj[u]) {
        if (v != p) {
            depth[v] = depth[u] + 1;
            dfs(v, u);
        }
    }
    tout[u] = timer++;
}

bool is_ancestor(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v) {
    if (is_ancestor(u, v))
        return u;
    if (is_ancestor(v, u))
        return v;
    for (int j = LOG-1; j >= 0; j--) {
        if (!is_ancestor(up[u][j], v))
            u = up[u][j];
    }
    return up[u][0];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;
    for (int i = 0; i < N-1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(0, 0);

    vector<long long> A(N);
    for (int i = 0; i < N; i++)
        cin >> A[i];

    vector<long long> prefix_A(N+1, 0);
    for (int i = 0; i < N; i++)
        prefix_A[i+1] = prefix_A[i] + A[i];

    int Q;
    cin >> Q;
    vector<long long> X(Q, 0);
    long long sum_X = 0;

    for (int i = 0; i < Q; i++) {
        long long a_prime, b_prime, k_prime;
        int delta_i;
        cin >> a_prime >> b_prime >> k_prime >> delta_i;

        long long a, b, k;
        if (i == 0) {
            a = a_prime;
            b = b_prime;
            k = k_prime;
        } else {
            a = (a_prime + sum_X) % N;
            b = (b_prime + 2*sum_X) % N;
            k = (k_prime + sum_X*sum_X) % 150001;
        }
        int l = min(a, b);
        int r = max(a, b) + 1;

        long long total_sum = prefix_A[r] - prefix_A[l] + k*(r - l);
        long long best = LLONG_MAX;
        int best_v = -1;

        for (int v = 0; v < N; v++) {
            long long current_sum = 0;
            for (int w = l; w < r; w++) {
                current_sum += (A[w] + k) * (depth[v] + depth[w] - 2 * depth[lca(v, w)]);
            }
            if (current_sum < best) {
                best = current_sum;
                best_v = v;
            } else if (current_sum == best && depth[v] < depth[best_v]) {
                best_v = v;
            }
        }

        X[i] = best_v;
        sum_X += X[i];
    }

    for (auto x : X)
        cout << x << '\n';

    return 0;
}
0