結果

問題 No.399 動的な領主
ユーザー suibakasuibaka
提出日時 2017-11-28 22:38:05
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 518 ms / 2,000 ms
コード長 4,079 bytes
コンパイル時間 2,500 ms
コンパイル使用メモリ 193,020 KB
実行使用メモリ 19,840 KB
最終ジャッジ日時 2024-11-27 13:16:39
合計ジャッジ時間 8,297 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 4 ms
5,248 KB
testcase_05 AC 31 ms
5,248 KB
testcase_06 AC 494 ms
14,720 KB
testcase_07 AC 518 ms
14,848 KB
testcase_08 AC 472 ms
14,976 KB
testcase_09 AC 484 ms
14,848 KB
testcase_10 AC 5 ms
5,248 KB
testcase_11 AC 25 ms
5,248 KB
testcase_12 AC 335 ms
15,488 KB
testcase_13 AC 322 ms
15,488 KB
testcase_14 AC 130 ms
19,616 KB
testcase_15 AC 179 ms
19,840 KB
testcase_16 AC 238 ms
17,408 KB
testcase_17 AC 484 ms
15,104 KB
testcase_18 AC 474 ms
14,936 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

typedef long long ll;

class HLD {
	vector<vector<int> > G;
	vector<int> vid, head, heavy, par, dep;
	int dfs(int v, int prev) {
		par[v] = prev;
		int cnt = 1, ma = 0;
		for (int to : G[v]) if (to != prev) {
			dep[to] = dep[v] + 1;
			int c = dfs(to, v);
			cnt += c;
			if (ma < c) {
				ma = c;
				heavy[v] = to;
			}
		}
		return cnt;
	}
public:
	HLD(int n) : G(n), vid(n, -1), head(n), heavy(n, -1), par(n), dep(n) {}
	void add(int u, int v) {
		G[u].push_back(v);
		G[v].push_back(u);
	}
	void build() {
		dfs(0, -1);
		int k = 0;
		queue<int> q;
		q.push(0);
		while (!q.empty()) {
			int h = q.front(); q.pop();
			for (int i = h; i != -1; i = heavy[i]) {
				vid[i] = k++;
				head[i] = h;
				for (int j : G[i]) if (j != par[i] && j != heavy[i]) q.push(j);
			}
		}
	}
	int operator[](int v) {
		return vid[v];
	}
    template <typename F> // F -> int -> int -> void
	void for_each(int u, int v, F f) {
		while (true) {
			if (vid[u] > vid[v]) swap(u, v);
			f(max(vid[head[v]], vid[u]), vid[v]);
			if (head[u] == head[v]) break;
			v = par[head[v]];
		}
	}
    template <typename F> // F -> int -> int -> int -> void
	void for_each_directed(int u, int v, F f) {
		while (true) {
			if (vid[u] > vid[v]) {
				f(max(vid[head[u]], vid[v]), vid[u], 1);
				if (head[u] == head[v]) break;
				u = par[head[u]];
			}
			else {
				f(max(vid[head[v]], vid[u]), vid[v], 0);
				if (head[u] == head[v]) break;
				v = par[head[v]];
			}
		}
	}
    template <typename F> // F -> int -> int -> void
	void for_each_edge(int u, int v, F f) {
		while (true) {
			if (vid[u] > vid[v]) swap(u, v);
			if (head[u] != head[v]) {
				f(vid[head[v]], vid[v]);
				v = par[head[v]];
			}
			else {
				if (u != v) f(vid[u] + 1, vid[v]);
				break;
			}
		}
	}
	//int ancestor(int u, int d) {
	//	while (true) {
	//		if (dep[head[u]] > dep[u] - d) {
	//			d -= dep[u] - dep[head[u]] + 1;
	//			if (head[u] == 0) return 0;
	//			u = par[head[u]];
	//		}
	//		else {
	//			return inv[vid[u] - d];
	//		}
	//	}
	//}
	int lca(int u, int v) {
		while (true) {
			if (vid[u] > vid[v]) swap(u, v);
			if (head[u] == head[v]) return u;
			v = par[head[v]];
		}
	}
	int distance(int u, int v) {
		return dep[u] + dep[v] - 2 * dep[lca(u, v)];
	}
};

template <typename T>
class LazySegmentTree {
	const int n;
	const T id;
	vector<T> data, data2;
	int size(int n) {
		int res = 1;
		while (res < n) res <<= 1;
		return res;
	}
	T sub(int l, int r, int node, int lb, int ub) {
		if (ub <= l || r <= lb) return id;
		if (l <= lb && ub <= r) {
			return data[node] + data2[node] * (ub - lb);
		}
		return data2[node] * (min(r, ub) - max(l, lb))
			+ sub(l, r, node * 2, lb, (lb + ub) / 2)
			+ sub(l, r, node * 2 + 1, (lb + ub) / 2, ub);
	}
	void suc(int l, int r, int node, int lb, int ub, T val) {
		if (ub <= l || r <= lb) return;
		if (l <= lb && ub <= r) {
			data2[node] += val;
			return;
		}
		data[node] += val * (min(r, ub) - max(l, lb));
		suc(l, r, node * 2, lb, (lb + ub) / 2, val);
		suc(l, r, node * 2 + 1, (lb + ub) / 2, ub, val);
	}
public:
	LazySegmentTree(int n_) :
		n(size(n_)), id(0), data(n * 2, id), data2(n * 2, id) {}
	void add(int l, int r, T val) {
		suc(l, r + 1, 1, 0, n, val);
	}
	T getSum(int l, int r) {
		return sub(l, r + 1, 1, 0, n);
	}
};

struct Function { // O͓Kł
	Function(ll& r, LazySegmentTree<ll>& seg)
		: res(r), lst(seg)
	{}
	ll& res;
	LazySegmentTree<ll>& lst;
	void operator()(int l, int r) {
		res += lst.getSum(l, r);
	}
};

struct Add {
	LazySegmentTree<ll>& lst;
	Add(LazySegmentTree<ll>& seg)
		: lst(seg)
	{}
	void operator()(int l, int r) {
		lst.add(l, r, 1);
	}
};

int main()
{
	ll N, Q, A, B;
	cin >> N;
	HLD hl(N);
	for (int i = 0, u, v; i < N - 1; i++) {
		cin >> u >> v;
		hl.add(u - 1, v - 1);
	}
	hl.build();
	LazySegmentTree<ll> lst(N);
	cin >> Q;
	ll res = 0;
	Function f(res, lst);
	Add add(lst);
	while (Q--) {
		cin >> A >> B; A--; B--;
		hl.for_each(A, B, f);
		res += hl.distance(A, B) + 1;
		hl.for_each(A, B, add);
	}
	cout << res << endl;
	return 0;
}
0