結果
| 問題 |
No.2258 The Jikka Tree
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:20:24 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,389 bytes |
| コンパイル時間 | 1,301 ms |
| コンパイル使用メモリ | 104,744 KB |
| 実行使用メモリ | 16,072 KB |
| 最終ジャッジ日時 | 2025-05-14 13:21:36 |
| 合計ジャッジ時間 | 14,774 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 11 WA * 8 TLE * 1 -- * 55 |
ソースコード
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath> // For log2 and pow
// For LCA
std::vector<std::vector<int>> adj;
std::vector<int> depth;
std::vector<int> parent_lca; // Renamed to avoid conflict
std::vector<std::vector<int>> up;
int N_nodes;
int LOGN_nodes;
// For centroid finding
std::vector<long long> current_query_subtree_sum_coeffs; // Stores W_sub(u) for current query
std::vector<int> A_vals;
int current_k_val;
int current_l_range, current_r_range;
void dfs_lca_prec(int u, int p, int d) {
depth[u] = d;
parent_lca[u] = p;
up[u][0] = p;
for (int i = 1; i < LOGN_nodes; ++i) {
if (up[u][i-1] != -1) {
up[u][i] = up[up[u][i-1]][i-1];
} else {
up[u][i] = -1;
}
}
for (int v : adj[u]) {
if (v != p) {
dfs_lca_prec(v, u, d + 1);
}
}
}
int get_lca(int u, int v) {
if (depth[u] < depth[v]) std::swap(u, v);
for (int i = LOGN_nodes - 1; i >= 0; --i) {
if (up[u][i] != -1 && depth[up[u][i]] >= depth[v]) {
u = up[u][i];
}
}
if (u == v) return u;
for (int i = LOGN_nodes - 1; i >= 0; --i) {
if (up[u][i] != -1 && up[v][i] != -1 && up[u][i] != up[v][i]) {
u = up[u][i];
v = up[v][i];
}
}
return parent_lca[u];
}
int get_dist_nodes(int u, int v) {
if (u == -1 || v == -1) return N_nodes + 7; // Effectively infinity for distance
int ancestor = get_lca(u, v);
return depth[u] + depth[v] - 2 * depth[ancestor];
}
void dfs_calc_subtree_sums(int u, int p) {
long long sum_val = 0;
if (u >= current_l_range && u < current_r_range) {
sum_val = (long long)A_vals[u] + current_k_val;
}
for (int v : adj[u]) {
if (v == p) continue;
dfs_calc_subtree_sums(v, u);
sum_val += current_query_subtree_sum_coeffs[v];
}
current_query_subtree_sum_coeffs[u] = sum_val;
}
int find_centroid_recursive(int u, int p, long long total_coeffs_sum_query) {
for (int v : adj[u]) {
if (v == p) continue;
if (current_query_subtree_sum_coeffs[v] * 2 > total_coeffs_sum_query) {
return find_centroid_recursive(v, u, total_coeffs_sum_query);
}
}
// If no child subtree is "too heavy", then u is a centroid.
// (This simplified version assumes current_query_subtree_sum_coeffs[u] correctly represents
// the sum of weights in the component rooted at u if we cut edge (p,u).
// If (total_coeffs_sum_query - current_query_subtree_sum_coeffs[u]) * 2 > total_coeffs_sum_query,
// then the centroid is actually p or further "up". But find_centroid is typically called on root of component.
// For finding centroid of the whole tree, starting at global root (0) is fine.
return u;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cin >> N_nodes;
adj.resize(N_nodes);
depth.resize(N_nodes);
parent_lca.resize(N_nodes);
LOGN_nodes = 0;
while ((1 << LOGN_nodes) <= N_nodes) LOGN_nodes++;
up.assign(N_nodes, std::vector<int>(LOGN_nodes, -1));
for (int i = 0; i < N_nodes - 1; ++i) {
int u_node, v_node;
std::cin >> u_node >> v_node;
adj[u_node].push_back(v_node);
adj[v_node].push_back(u_node);
}
A_vals.resize(N_nodes);
for (int i = 0; i < N_nodes; ++i) {
std::cin >> A_vals[i];
}
dfs_lca_prec(0, -1, 0);
current_query_subtree_sum_coeffs.resize(N_nodes);
int Q_val;
std::cin >> Q_val;
long long sum_X_prev_queries = 0;
long long MOD_K = 150001;
for (int i = 0; i < Q_val; ++i) {
long long ap, bp, kp_prime;
int delta_node;
std::cin >> ap >> bp >> kp_prime >> delta_node;
long long cur_a_param, cur_b_param;
if (i == 0) {
cur_a_param = ap;
cur_b_param = bp;
current_k_val = kp_prime;
} else {
cur_a_param = (ap + sum_X_prev_queries) % N_nodes;
cur_b_param = (bp + 2 * sum_X_prev_queries) % N_nodes;
long long sum_X_mod_k = sum_X_prev_queries % MOD_K;
current_k_val = (kp_prime + sum_X_mod_k * sum_X_mod_k) % MOD_K;
}
current_l_range = std::min(cur_a_param, cur_b_param);
current_r_range = 1 + std::max(cur_a_param, cur_b_param);
dfs_calc_subtree_sums(0, -1);
long long total_sum_coeffs = current_query_subtree_sum_coeffs[0];
int c1 = -1, c2 = -1;
if (total_sum_coeffs == 0) {
c1 = delta_node;
} else {
c1 = find_centroid_recursive(0, -1, total_sum_coeffs);
// Check for a second centroid c2
// c2 exists if an edge $(c1, c2')$ splits weights perfectly.
// This means sum of weights in component of $c2'$ is $W_{total}/2$.
// This component is subtree $c2'$ if $c2'$ is child of $c1$.
// Or it's "everything not in $c1$'s subtree" if $c2'$ is parent of $c1$.
// Check parent direction: if c1 is not root (0) and parent_lca[c1] is valid
if (parent_lca[c1] != -1) {
if ((total_sum_coeffs - current_query_subtree_sum_coeffs[c1]) * 2 == total_sum_coeffs) {
c2 = parent_lca[c1];
}
}
// Check children direction (if c2 not found via parent)
if (c2 == -1) { // c2 still not found
for (int child_of_c1 : adj[c1]) {
if (child_of_c1 == parent_lca[c1]) continue;
if (current_query_subtree_sum_coeffs[child_of_c1] * 2 == total_sum_coeffs) {
c2 = child_of_c1;
break;
}
}
}
}
int best_v_ans;
if (c2 == -1 || c1 == c2) {
best_v_ans = c1;
} else {
int dist1_to_delta = get_dist_nodes(c1, delta_node);
int dist2_to_delta = get_dist_nodes(c2, delta_node);
if (dist1_to_delta <= dist2_to_delta) {
best_v_ans = c1;
} else {
best_v_ans = c2;
}
}
std::cout << best_v_ans << "\n";
sum_X_prev_queries += best_v_ans;
}
return 0;
}