#line 1 "playground_A.cpp" #include #line 1 "/home/samejima/CompetitiveProgramming/library/graph/tree/heavy_light_decomposition.hpp" #include #include #include #include #line 1 "/home/samejima/CompetitiveProgramming/library/graph/graph_template.hpp" #line 5 "/home/samejima/CompetitiveProgramming/library/graph/graph_template.hpp" template struct Edge { int from; int to; T cost; Edge(int _from, int _to, T _cost) : from(_from), to(_to), cost(_cost) {} // unweighted Edge(int _from, int _to) : from(_from), to(_to), cost(T(1)) {} bool operator==(const Edge& rhs) { return from == rhs.from && to == rhs.to && cost == rhs.cost; } }; template struct Graph : std::vector>> { using std::vector>>::vector; // inherit constructors void add_edge(int i, Edge e) { (*this)[i].push_back(e); } // weighted void add_edge(int _from, int _to, T _cost) { (*this)[_from].push_back(Edge(_from, _to, _cost)); } // unweighted void add_edge(int _from, int _to) { (*this)[_from].push_back(Edge(_from, _to, T(1))); } }; #line 10 "/home/samejima/CompetitiveProgramming/library/graph/tree/heavy_light_decomposition.hpp" // cf : https://ngtkana.hatenablog.com/entry/2024/06/24/200138 struct Interval { // i : interval のもっとも根に近い頂点のid // j : interval のもっとも葉に近い頂点のid // last : LCAを含む interval であるかどうか // reverse : from → to と i → jが逆向きかどうか int i, j; bool last; bool reverse; Interval(int _i, int _j, bool _last, bool _reverse) : i(_i), j(_j), last(_last), reverse(_reverse) { } }; using Path = std::vector; struct HLD { //vector>children; std::vectorparent; std::vector id; std::vector id2; std::vector head; std::vectordepth; Graphgraph; HLD (int N) : parent(std::vector(N, -1)), id(std::vector(N)), id2(std::vector(N)), head(std::vector(N)), depth(std::vector(N)), graph(N) {} void build(int root=0) { dfs_sz(root); int k = 0; dfs_hld(root, k); } int dfs_sz(int v) { int ret = 1, mx_sz = 0; for (Edge& nxt : graph[v]) { if (nxt.to == parent[v]) continue; parent[nxt.to] = v; depth[nxt.to] = depth[v] + 1; int sz = dfs_sz(nxt.to); ret += sz; if (mx_sz < sz) { mx_sz = sz; std::swap(graph[v][0], nxt); } } return ret; } void dfs_hld(int v, int& k) { id[v] = k; k++; for (Edge e : graph[v]) { if (e.to == parent[v]) continue; head[e.to] = (e == graph[v][0] ? head[v] : e.to); dfs_hld(e.to, k); } id2[v] = k; } int lca(int u, int v) { while (true) { if (id[u] > id[v]) std::swap(u, v); if (head[u] == head[v]) return u; v = parent[head[v]]; } } Path get_path(int u, int v) { Path upath, vpath; while (head[u] != head[v]) { // ちなみにu,vのdepthの大小関係は変わり続けることもある。 // 10 → 12など。 // v's head is deeper if (depth[head[v]] >= depth[head[u]]) { assert(depth[head[v]] >= depth[head[u]]); /* / : heavy edge .... : light edge head[u] / /... u ... / head[v] / \ / \ / v */ // u→v なのでreverse=false vpath.emplace_back(id[head[v]], id[v], false, false); v = parent[head[v]]; } // u's head is deeper else if (depth[head[v]] < depth[head[u]]) { /* / : heavy edge .... : light edge head[v] / /... v ... / head[u] / \ / \ / u */ // upath.emplace_back(id[head[u]], id[u], false, true); u = parent[head[u]]; } } // v is deeper /* u / / ←↓ / v */ if (depth[v] > depth[u]) { upath.emplace_back(id[u], id[v], true, false); } // u is deeper /* v / / →↑ / u */ else { upath.emplace_back(id[v], id[u], true, true); } Path retpath = upath; reverse(vpath.begin(), vpath.end()); for (Interval path : vpath) retpath.push_back(path); return retpath; } std::pair subtree_query(int r) { assert(r < int(id.size())); return std::make_pair(id[r], id2[r]); } }; #line 3 "playground_A.cpp" using namespace std; int main() { int N; cin >> N; HLD hld(N); for (int i=0; i> u >> v; u--; v--; hld.graph.add_edge(u,v); hld.graph.add_edge(v,u); } hld.build(); vector cusum(N+1); int Q; cin >> Q; for (int q=0; q> A >> B; A--; B--; for (Interval intv : hld.get_path(A,B)) { cusum[intv.i] += 1; cusum[intv.j+1] -= 1; } } long ans = 0; for (int i=0; i