結果

問題 No.399 動的な領主
ユーザー mayoko_mayoko_
提出日時 2016-07-18 17:56:49
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 487 ms / 2,000 ms
コード長 6,937 bytes
コンパイル時間 1,979 ms
コンパイル使用メモリ 125,140 KB
実行使用メモリ 50,264 KB
最終ジャッジ日時 2024-11-07 19:34:49
合計ジャッジ時間 6,863 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 27 ms
7,040 KB
testcase_06 AC 486 ms
41,660 KB
testcase_07 AC 478 ms
41,656 KB
testcase_08 AC 454 ms
42,260 KB
testcase_09 AC 459 ms
42,352 KB
testcase_10 AC 4 ms
5,248 KB
testcase_11 AC 19 ms
8,140 KB
testcase_12 AC 312 ms
50,264 KB
testcase_13 AC 308 ms
50,116 KB
testcase_14 AC 127 ms
49,636 KB
testcase_15 AC 207 ms
49,640 KB
testcase_16 AC 228 ms
49,240 KB
testcase_17 AC 461 ms
42,228 KB
testcase_18 AC 487 ms
42,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
//#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
//#include<list>
#include<queue>
#include<deque>
#include<algorithm>
//#include<numeric>
#include<utility>
//#include<memory>
#include<functional>
#include<cassert>
#include<set>
#include<stack>
#include<random>

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, -1, 0, 1};
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;

class Tree {
public:
    Tree(int V, int root) : V(V), root(root) {
        T.resize(V);
        for (int i = 0; i < MAXLOGV; i++) parent[i].resize(V);
        depth.resize(V);
    }
    // uとvをつなぐ
    // lcaを求めることが主目的なので無向グラフとしている
    void unite(int u, int v) {
        T[u].push_back(v);
        T[v].push_back(u);
    }
    // initする
    // コンストラクタだけじゃなくてこれも呼ばないとlcaが求められないぞ
    void init() {
        dfs(root, -1, 0);
        for (int k = 0; k+1 < MAXLOGV; k++) {
            for (int v = 0; v < V; v++) {
                if (parent[k][v] < 0) parent[k+1][v] = -1;
                else parent[k+1][v] = parent[k][parent[k][v]];
            }
        }
    }
    // uとvのlcaを求める
    int lca(int u, int v) const {
        if (depth[u] > depth[v]) swap(u, v);
        for (int k = 0; k < MAXLOGV; k++) {
            if ((depth[v] - depth[u])>>k & 1) {
                v = parent[k][v];
            }
        }
        if (u == v) return u;
        for (int k = MAXLOGV-1; k >= 0; k--) {
            if (parent[k][u] != parent[k][v]) {
                u = parent[k][u];
                v = parent[k][v];
            }
        }
        return parent[0][u];
    }
    // uとvの距離を求める
    // edgeを定義しないといけない時はこれじゃダメ
    int dist(int u, int v) const {
        int p = lca(u, v);
        return (depth[u]-depth[p]) + (depth[v]-depth[p]);
    }
    void dfs(int v, int p, int d) {
        parent[0][v] = p;
        depth[v] = d;
        for (int next : T[v]) {
            if (next != p) dfs(next, v, d+1);
        }
    }
    static const int MAXLOGV = 25;
    // グラフの隣接リスト表現
    vector<vector<int> > T;
    // 頂点の数
    int V;
    // 根ノードの番号
    int root;

    // 親ノード
    vector<int> parent[MAXLOGV];
    // 根からの深さ
    vector<int> depth;
};


// 遅延評価つきセグメント木
// update: [l, r) の区間に値 v を一様に追加する
// query:  [l, r) の区間の和を求める
struct ST {
    vector<ll> seg, lazy;
    int size;

	ST() {}
    ST(int n) {
        size = 1;
        while (size < n) size *= 2;
        seg.resize(size * 2);
        lazy.resize(size * 2);
    }

    inline void push(int k, int l, int r) {
        if (lazy[k] != 0) {
            seg[k] += lazy[k] * (r - l);
            if (r - l > 1) {
                lazy[k * 2 + 1] += lazy[k];
                lazy[k * 2 + 2] += lazy[k];
            }
            lazy[k] = 0;
        }
    }

    inline ll merge(ll x, ll y) {
        return x + y;
    }

    void update(int a, int b, ll v, int k, int l, int r) {
        push(k, l, r);
        if (r <= a || b <= l) return;
        if (a <= l && r <= b) {
            lazy[k] += v;
            push(k, l, r);
        } else {
            update(a, b, v, k * 2 + 1, l, (l + r) / 2);
            update(a, b, v, k * 2 + 2, (l + r) / 2, r);
            seg[k] = merge(seg[k * 2 + 1], seg[k * 2 + 2]);
        }
    }

    void update(int a, int b, ll v) {
        return update(a, b, v, 0, 0, size);
    }

    ll query(int a, int b, int k, int l, int r) {
        push(k, l, r);
        if (r <= a || b <= l) return 0;
        if (a <= l && r <= b) return seg[k];
        ll x = query(a, b, k * 2 + 1, l, (l + r) / 2);
        ll y = query(a, b, k * 2 + 2, (l + r) / 2, r);
        return merge(x, y);
    }

    ll query(int a, int b) {
        return query(a, b, 0, 0, size);
    }
};


class HeavyLightDecomposition {
public:
	struct heavy_set {
		vector<int> element;
		int depth;
		int parent_vertex;
		heavy_set(int v, int d, int par) : element(1, v), depth(d), parent_vertex(par) {}
	};
	vector<vector<int>> G;
	vector<heavy_set> S;
	vector<int> subtree_size;
	vector<int> set_index;
	vector<int> ele_index;
private:
	int get_subtree_size(int v, int p) {
		int& sz = subtree_size[v];
		if (sz > 0) return sz;
		sz = 1;
		for (int ch : G[v]) if (ch != p) {
			sz += get_subtree_size(ch, v);
		}
		return sz;
	}

	void make_path(int v, int p, int set_id) {
		set_index[v] = set_id;
		ele_index[v] = S[set_id].element.size() - 1;

		int largest_child = -1, maxi = 0;

		for (int ch : G[v]) if (ch != p) {
			if (maxi < get_subtree_size(ch, v)) {
				maxi = subtree_size[ch];
				largest_child = ch;
			}
		}

		for (int ch : G[v]) if (ch != p) {
			if (largest_child == ch) {
				S[set_id].element.push_back(ch);
				make_path(ch, v, set_id);
			}
			else {
				S.emplace_back(ch, S[set_id].depth + 1, v);
				make_path(ch, v, S.size() - 1);
			}
		}
	}

	void init(int root) {
		subtree_size.resize(G.size());
		set_index.resize(G.size());
		ele_index.resize(G.size());

		S.emplace_back(root, 0, root);
		make_path(root, root, 0);

		subtree_size.clear();
	}

public:
	HeavyLightDecomposition(const vector<vector<int>>& G, int root = 0) : G(G) {
		init(root);
	}
	pair<int, int> get_position(int v) {
		return pair<int, int>(set_index[v], ele_index[v]);
	}
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
	int N;
	cin >> N;
	vector<vector<int> > G(N);
	Tree tree(N, 0);
	for (int i = 0; i < N - 1; i++) {
		int u, v;
		cin >> u >> v;
		u--; v--;
		G[u].push_back(v);
		G[v].push_back(u);
		tree.unite(u, v);
	}
	tree.init();
	HeavyLightDecomposition hld(G);
	vector<ST> seg;
	for (int i = 0; i < hld.S.size(); i++) {
		seg.emplace_back(hld.S[i].element.size());
	}

	ll ans = 0;
	int Q;
	cin >> Q;
	while (Q--) {
		int u, v;
		cin >> u >> v;
		u--; v--;
		int lca = tree.lca(u, v);
		while (hld.get_position(v).first != hld.get_position(lca).first) {
			pii tmp = hld.get_position(v);
			seg[tmp.first].update(0, tmp.second+1, 1);
			ans += seg[tmp.first].query(0, tmp.second + 1);

			v = hld.S[tmp.first].parent_vertex;
		}
		while (hld.get_position(u).first != hld.get_position(lca).first) {
			pii tmp = hld.get_position(u);
			seg[tmp.first].update(0, tmp.second+1, 1);
			ans += seg[tmp.first].query(0, tmp.second + 1);

			u = hld.S[tmp.first].parent_vertex;
		}
		pii tu = hld.get_position(u), tv = hld.get_position(v);
		int mini = min(tu.second, tv.second), maxi = max(tu.second, tv.second);
		seg[tu.first].update(mini, maxi + 1, 1);
		ans += seg[tu.first].query(mini, maxi + 1);
	}

	cout << ans << endl;

    return 0;
}
0