結果

問題 No.399 動的な領主
ユーザー ku_senjanku_senjan
提出日時 2023-12-28 23:22:23
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 748 ms / 2,000 ms
コード長 2,637 bytes
コンパイル時間 6,075 ms
コンパイル使用メモリ 274,620 KB
実行使用メモリ 22,824 KB
最終ジャッジ日時 2023-12-28 23:22:37
合計ジャッジ時間 12,922 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,676 KB
testcase_01 AC 2 ms
6,676 KB
testcase_02 AC 2 ms
6,676 KB
testcase_03 AC 2 ms
6,676 KB
testcase_04 AC 4 ms
6,676 KB
testcase_05 AC 42 ms
6,676 KB
testcase_06 AC 700 ms
17,856 KB
testcase_07 AC 707 ms
17,856 KB
testcase_08 AC 688 ms
17,908 KB
testcase_09 AC 720 ms
17,900 KB
testcase_10 AC 6 ms
6,676 KB
testcase_11 AC 35 ms
6,676 KB
testcase_12 AC 519 ms
18,344 KB
testcase_13 AC 522 ms
18,324 KB
testcase_14 AC 161 ms
22,824 KB
testcase_15 AC 207 ms
22,824 KB
testcase_16 AC 306 ms
20,304 KB
testcase_17 AC 748 ms
17,892 KB
testcase_18 AC 718 ms
17,904 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

class HeavyLightDecomposition{
	private:
		int n;
		vector<vector<int>> g;
		vector<int> siz, par, dep, top, in, out;

		void dfs_siz(int v, int p){
			par[v] = p;
			for(int &nv:g[v]){
				if(nv==p){
					if(nv==g[v].back()) break;
					swap(nv, g[v].back());
				}
				dfs_siz(nv, v);
				siz[v] += siz[nv];
				if(siz[nv]>siz[g[v][0]]){
					swap(nv, g[v][0]);
				}
			}
		}

		void dfs_hld(int v, int p, int &i){
			in[v] = i++;
			for(int &nv:g[v]){
				if(nv==p) continue;
				dep[nv] = dep[v]+1;
				if(nv==g[v][0]) top[nv] = top[v];
				else top[nv] = nv;
				dfs_hld(nv, v, i);
			}
			out[v] = i;
		}

	public:
		HeavyLightDecomposition(const int _n=0):
			n(_n), g(_n), siz(_n, 1), par(_n, -1),
			dep(_n), top(_n), in(_n), out(_n){}

		void add_edge(int u, int v){
			g[u].push_back(v);
			g[v].push_back(u);
		}

		void build(){
			dfs_siz(0, -1);
			int i{};
			dfs_hld(0, -1, i);
		}

		int depth(int v) const {
			return dep[v];
		}

		int lca(int u, int v) const {
			while(true){
				if(in[u]>in[v]) swap(u, v);
				if(top[u]==top[v]) return u;
				v = par[top[v]];
			}
		}

		void subtree_query(int u, const function<void(int,int)> &func) const{
			func(in[u], out[u]);
		}

		void path_node_query(int u, int v, const function<void(int,int)> &func) const {
			while(true){
				if(in[u]>in[v]) swap(u, v);
				func(max(in[u], in[top[v]]), in[v]+1);
				if(top[u]==top[v]) break;
				v = par[top[v]];
			}
		}

		void path_edge_query(int u, int v, const function<void(int,int)> &func) const {
			while(true){
				if(in[u]>in[v]) swap(u, v);
				if(top[u]==top[v]){
					if(u==v) break;
					func(in[u]+1, in[v]+1);
				}else{
					func(in[top[v]], in[v]+1);
					v = par[top[v]];
				}
			}
		}
};

struct S{
	long long value;
	int size;
};
using F = long long;

S op(S a, S b){ return {a.value+b.value, a.size+b.size}; }
S e(){ return {0, 0}; }
S mapping(F f, S x){ return {x.value + f*x.size, x.size}; }
F composition(F f, F g){ return f+g; }
F id(){ return 0; }

int main(){
	int N; cin >> N;
	HeavyLightDecomposition hld(N);
	for(int i=0; i<N-1; i++){
		int u, v; cin >> u >> v;
		u--, v--;
		hld.add_edge(u, v);
	}

	hld.build();
	vector<S> v(N, {0, 1});
	lazy_segtree<S, op, e, F, mapping, composition, id> seg(v);
	long long ans = 0;

	int Q; cin >> Q;
	for(;Q--;){
		int u, v; cin >> u >> v;
		u--, v--;
		hld.path_node_query(u, v, [&](int a, int b) -> void{
				seg.apply(a, b, 1);
				});
		hld.path_node_query(u, v, [&](int a, int b) -> void{
				ans += seg.prod(a, b).value;
				});
	}

	cout << ans << endl;
}
0