#include #include #include #include const int INF = 1000*1000*1000; typedef vector < vector > graph; vector dfs_list; vector ribs_list; vector h; void dfs (int v, const graph & g, const graph & rib_ids, int cur_h = 1) { h[v] = cur_h; dfs_list.push_back (v); for (size_t i=0; i lca_tree; vector first; void lca_tree_build (int i, int l, int r) { if (l == r) lca_tree[i] = dfs_list[l]; else { int m = (l + r) >> 1; lca_tree_build (i+i, l, m); lca_tree_build (i+i+1, m+1, r); int lt = lca_tree[i+i], rt = lca_tree[i+i+1]; lca_tree[i] = h[lt] < h[rt] ? lt : rt; } } void lca_prepare (int n) { lca_tree.assign (dfs_list.size() * 8, -1); lca_tree_build (1, 0, (int)dfs_list.size()-1); first.assign (n, -1); for (int i=0; i < (int)dfs_list.size(); ++i) { int v = dfs_list[i]; if (first[v] == -1) first[v] = i; } } int lca_tree_query (int i, int tl, int tr, int l, int r) { if (tl == l && tr == r) return lca_tree[i]; int m = (tl + tr) >> 1; if (r <= m) return lca_tree_query (i+i, tl, m, l, r); if (l > m) return lca_tree_query (i+i+1, m+1, tr, l, r); int lt = lca_tree_query (i+i, tl, m, l, m); int rt = lca_tree_query (i+i+1, m+1, tr, m+1, r); return h[lt] < h[rt] ? lt : rt; } int lca (int a, int b) { if (first[a] > first[b]) swap (a, b); return lca_tree_query (1, 0, (int)dfs_list.size()-1, first[a], first[b]); } vector first1, first2; vector rib_used; vector tree1, tree2; void query_prepare (int n) { first1.resize (n-1, -1); first2.resize (n-1, -1); for (int i = 0; i < (int) ribs_list.size(); ++i) { int j = ribs_list[i]; if (first1[j] == -1) first1[j] = i; else first2[j] = i; } rib_used.resize (n-1); tree1.resize (ribs_list.size() * 8); tree2.resize (ribs_list.size() * 8); } void sum_tree_update (vector & tree, int i, int l, int r, int j, int delta) { tree[i] += delta; if (l < r) { int m = (l + r) >> 1; if (j <= m) sum_tree_update (tree, i+i, l, m, j, delta); else sum_tree_update (tree, i+i+1, m+1, r, j, delta); } } int sum_tree_query (const vector & tree, int i, int tl, int tr, int l, int r) { if (l > r || tl > tr) return 0; if (tl == l && tr == r) return tree[i]; int m = (tl + tr) >> 1; if (r <= m) return sum_tree_query (tree, i+i, tl, m, l, r); if (l > m) return sum_tree_query (tree, i+i+1, m+1, tr, l, r); return sum_tree_query (tree, i+i, tl, m, l, m) + sum_tree_query (tree, i+i+1, m+1, tr, m+1, r); } int query (int v1, int v2) { return sum_tree_query (tree1, 1, 0, (int)ribs_list.size()-1, first[v1], first[v2]-1) - sum_tree_query (tree2, 1, 0, (int)ribs_list.size()-1, first[v1], first[v2]-1); } int main() { // чтение графа int n; scanf ("%d", &n); graph g (n), rib_ids (n); for (int i=0; i