結果

問題 No.399 動的な領主
ユーザー leaf_1415leaf_1415
提出日時 2019-05-08 02:39:52
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,411 ms / 2,000 ms
コード長 5,372 bytes
コンパイル時間 1,496 ms
コンパイル使用メモリ 99,440 KB
実行使用メモリ 51,840 KB
最終ジャッジ日時 2024-07-02 00:24:31
合計ジャッジ時間 13,550 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 7 ms
9,600 KB
testcase_01 AC 7 ms
9,600 KB
testcase_02 AC 7 ms
9,728 KB
testcase_03 AC 7 ms
9,600 KB
testcase_04 AC 11 ms
9,856 KB
testcase_05 AC 73 ms
11,648 KB
testcase_06 AC 1,411 ms
31,936 KB
testcase_07 AC 1,379 ms
32,036 KB
testcase_08 AC 1,329 ms
32,056 KB
testcase_09 AC 1,286 ms
32,052 KB
testcase_10 AC 14 ms
9,728 KB
testcase_11 AC 55 ms
11,904 KB
testcase_12 AC 870 ms
32,796 KB
testcase_13 AC 841 ms
32,772 KB
testcase_14 AC 244 ms
51,840 KB
testcase_15 AC 300 ms
51,712 KB
testcase_16 AC 487 ms
41,988 KB
testcase_17 AC 1,350 ms
32,132 KB
testcase_18 AC 1,314 ms
32,052 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <map>
#define llint long long

using namespace std;

typedef pair<int, int> P;

struct HLD{
	int V, logV;
	vector<P> mp;
	map<P, int> mp2;
	vector<P> parent;
	
	//subtree of v is [pre_order[v], back_order[v]]
	vector<int> pre_order;
	vector<int> back_order;
	
	int order;
	int global_id, local_id;
	vector<int> size, depth;
	vector<vector<int> > prev;
	
	HLD(){}
	
	void predfs(vector<int> G[], int v, int p, int d)
	{
		size[v] = 1, depth[v] = d, prev[v][0] = p;
		for(int i = 0; i < G[v].size(); i++){
			if(G[v][i] == p) continue;
			predfs(G, G[v][i], v, d+1);
			size[v] += size[G[v][i]];
		}
	}
	void maindfs(vector<int> G[], int v, int p)
	{
		mp[v] = make_pair(global_id, local_id);
		mp2[make_pair(global_id, local_id)] = v;
		pre_order[v] = ++order;
		
		if(G[v].size() == 1 && G[v][0] == p){
			back_order[v] = order;
			return;
		}
		
		vector<P> vec;
		for(int i = 0; i < G[v].size(); i++){
			if(G[v][i] == p) continue;
			vec.push_back(make_pair(size[G[v][i]], G[v][i]));
		}
		sort(vec.rbegin(), vec.rend());
		
		local_id++;
		maindfs(G, vec[0].second, v);
		
		for(int i = 1; i < vec.size(); i++){
			parent.push_back(mp[v]);
			global_id++, local_id = 0;
			maindfs(G, vec[i].second, v);
		}
		back_order[v] = order;
	}
	int getLCA(int u, int v){
		int x = u, y = v;
		if(depth[y] > depth[x]) swap(x, y);
		
		for(int i = logV-1; i >= 0; i--){
			if(depth[x] - (1<<i) >= depth[y]) x = prev[x][i];
		}
		if(x == y) return x;
		for(int i = logV-1; i >= 0; i--){
			if(prev[x][i] != prev[y][i]){
				x = prev[x][i];
				y = prev[y][i];
			}
		}
		x = prev[x][0];
		return x;
	}
	void pathcalc(int v, int lca, vector<pair<int, P> > &dest)
	{
		int gid = mp[v].first, lid = mp[v].second;
		int Gid = mp[lca].first, Lid = mp[lca].second;
		
		while(Gid != gid){
			dest.push_back(make_pair(gid, make_pair(0, lid)));
			int ngid = parent[gid].first, nlid = parent[gid].second;
			gid = ngid, lid = nlid;
		}
		dest.push_back(make_pair(gid, make_pair(Lid, lid)));
	}
	
	void init(vector<int> G[], int V) // The tree must be 1-indexed.
	{
		this->V = V, logV = 0;
		for(int t = V; t; t/=2) logV++;
		prev.resize(V+1);
		for(int i = 0; i <= V; i++) prev[i].resize(logV);
		
		size.resize(V+1), depth.resize(V+1);
		predfs(G, 1, 0, 0);
		
		prev[0][0] = 0;
		for(int i = 1; i < logV; i++){
			for(int j = 1; j <= V; j++){
				prev[j][i] = prev[prev[j][i-1]][i-1];
			}
		}
		
		mp.resize(V+1), mp2.clear();
		parent.clear(), parent.push_back(make_pair(-1, -1));
		pre_order.resize(V+1), back_order.resize(V+1);
		global_id = local_id = 0, order = 0;
		
		maindfs(G, 1, 0);
	}
	
	void path(int u, int v, vector<pair<int, P> > &dest)
	{
		dest.clear();
		int lca = getLCA(u, v);
		pathcalc(u, lca, dest);
		pathcalc(v, lca, dest);
		
		pair<int, P> p = make_pair(mp[lca].first, make_pair(mp[lca].second, mp[lca].second));
		for(int i = 0; i < dest.size(); i++){
			if(dest[i] == p){
				dest.erase(dest.begin()+i);
				return ;
			}
		}
	}
	
	void toOrder(vector<pair<int, P> > &src, vector<P> &dest)
	{
		dest.clear();
		for(int i = 0; i < src.size(); i++){
			int u = mp2[make_pair(src[i].first, src[i].second.first)], v = mp2[make_pair(src[i].first, src[i].second.second)];
			dest.push_back(make_pair(pre_order[u], pre_order[v]));
		}
	}
};

// range-add, range-min query

struct SegTree{
	int size;
	vector<llint> seg, delay;
	
	SegTree(){}
	SegTree(int size){
		this->size = size;
		seg.resize(1<<(size+1));
		delay.resize(1<<(size+1));
	}
	
	void init()
	{
		for(int i = 0; i < (1<<(size+1)); i++){
			seg[i] = 0;
			delay[i] = 0;
		}
	}
	
	void eval(int l, int r, int k)
	{
		if(delay[k]){
			seg[k] += delay[k] * (r-l+1);
			if(l < r){
				delay[k*2] += delay[k];
				delay[k*2+1] += delay[k];
			}
			delay[k] = 0;
		}
	}
	
	void update(int i, llint val)
	{
		i += (1 << size);
		seg[i] = val;
		while(i > 1){
			i /= 2;
			seg[i] = seg[i*2] + seg[i*2+1];
		}
	}
	
	void add(int a, int b, int k, int l, int r, llint val)
	{
		eval(l, r, k);
		
		if(b < l || r < a) return;
		if(a <= l && r <= b){
			delay[k] += val;
			eval(l, r, k);
			return;
		}
		add(a, b, k*2, l, (l+r)/2, val);
		add(a, b, k*2+1, (l+r)/2+1, r, val);
		seg[k] = seg[k*2] + seg[k*2+1];
	}
	void add(int a, int b, llint val){
		if(a > b) return;
		add(a, b, 1, 0, (1<<size)-1, val);
	}

	llint query(int a, int b, int k, int l, int r)
	{
		eval(l, r, k);
		
		if(b < l || r < a) return 0;
		if(a <= l && r <= b) return seg[k];
		llint lval = query(a, b, k*2, l, (l+r)/2);
		llint rval = query(a, b, k*2+1, (l+r)/2+1, r);
		return lval + rval;
	}
	llint query(int a, int b)
	{
		return query(a, b, 1, 0, (1<<size)-1);
	}
};

int n, Q;
vector<int> G[100005];
HLD hld;
SegTree seg(17);

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	int u, v;
	for(int i = 1; i <= n-1; i++){
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	
	hld.init(G, n);
	seg.add(1, n, 1);
	
	cin >> Q;
	llint ans = 0;
	for(int q = 0; q < Q; q++){
		cin >> u >> v;
		
		vector<pair<int, P> > vec;
		vector<P> vec2;
		hld.path(u, v, vec);
		hld.toOrder(vec, vec2);
		
		for(int i = 0; i < vec2.size(); i++){
			ans += seg.query(vec2[i].first, vec2[i].second);
		}
		for(int i = 0; i < vec2.size(); i++){
			seg.add(vec2[i].first, vec2[i].second, 1);
		}
	}
	cout << ans << endl;
	
	return 0;
}
0