結果
| 問題 |
No.399 動的な領主
|
| コンテスト | |
| ユーザー |
 はまやんはまやん
|
| 提出日時 | 2017-04-10 18:03:38 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,411 bytes |
| コンパイル時間 | 1,979 ms |
| コンパイル使用メモリ | 183,448 KB |
| 実行使用メモリ | 24,400 KB |
| 最終ジャッジ日時 | 2024-07-18 05:41:42 |
| 合計ジャッジ時間 | 7,709 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 3 WA * 16 |
ソースコード
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
typedef long long ll;
struct LazySegTreeAddSetSum { // 全部[l,r]
struct Data {
ll val, add, sum; bool valset;
ll calc_sum(int l, int r) { if (valset) return (val + add) * (r - l + 1); else return sum + add * (r - l + 1); }
void set_data(int x, int y) { val = x; add = 0; valset = true; }
Data() :val(0), add(0), sum(0), valset(false) {}
};
vector<Data> data; int seg_size;
LazySegTreeAddSetSum(int n) {
for (seg_size = 1; seg_size < n; seg_size *= 2);
data.assign(seg_size * 2, Data());
}
ll set(int a, int b, ll x, int l = 0, int r = -1, int k = 0) {
if (r == -1) r = seg_size - 1;
if (a <= l && r <= b) { data[k].set_data(x, 0); return data[k].calc_sum(l, r); }
if (r < a || b < l) return data[k].calc_sum(l, r);
if (data[k].valset) {
data[k * 2 + 1].set_data(data[k].val, data[k].add);
data[k * 2 + 2].set_data(data[k].val, data[k].add);
}
data[k].add = 0; data[k].valset = false;
data[k].sum = set(a, b, x, l, (l + r) / 2, k * 2 + 1) + set(a, b, x, (l + r) / 2 + 1, r, k * 2 + 2);
return data[k].calc_sum(l, r);
}
ll add(int a, int b, ll x, int l = 0, int r = -1, int k = 0) {
if (r == -1) r = seg_size - 1;
if (a <= l && r <= b) { data[k].add += x; return data[k].calc_sum(l, r); }
if (r < a || b < l) return 0;
if (data[k].valset) {
data[k * 2 + 1].set_data(data[k].val, 0);
data[k * 2 + 2].set_data(data[k].val, 0);
data[k].valset = false;
}
data[k].sum = add(a, b, x, l, (l + r) / 2, k * 2 + 1) + add(a, b, x, (l + r) / 2 + 1, r, k * 2 + 2);
return data[k].calc_sum(l, r);
}
ll query(int a, int b, int l = 0, int r = -1, int k = 0) {
if (r == -1) r = seg_size - 1;
if (r < a || b < l) return 0;
if ((a <= l && r <= b) || data[k].valset) return data[k].calc_sum(max(a, l), min(b, r));
return query(a, b, l, (l + r) / 2, k * 2 + 1) + query(a, b, (l + r) / 2 + 1, r, k * 2 + 2) +
data[k].add * (min(b, r) - max(a, l) + 1);
}
};
//-----------------------------------------------------------------------------------
struct HLDecomposition {
vector<vector<int>> g;
// vid, head, heavy, parent は必須
// depth, inv は使用する機能によっては不要
vector<int> vid, head, heavy, parent, depth, inv;
HLDecomposition(int n) : g(n), vid(n, -1), head(n), heavy(n, -1), parent(n), depth(n), inv(n) {}
// 辺 (u, v) を追加する
void add(int u, int v) {
g[u].push_back(v);
g[v].push_back(u);
}
// 構築する
void build() {
dfs(0, -1);
bfs();
}
int dfs(int curr, int prev) {
parent[curr] = prev;
int sub = 1, max_sub = 0;
for (int next : g[curr]) if (next != prev) {
depth[next] = depth[curr] + 1;
int sub_next = dfs(next, curr);
sub += sub_next;
if (max_sub < sub_next) max_sub = sub_next, heavy[curr] = next;
}
return sub;
}
void bfs() {
int k = 0;
queue<int> q({ 0 });
while (!q.empty()) {
int h = q.front(); q.pop();
for (int i = h; i != -1; i = heavy[i]) {
vid[i] = k++;
inv[vid[i]] = i;
head[i] = h;
for (int j : g[i]) if (j != parent[i] && j != heavy[i]) q.push(j);
}
}
}
// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
// 以下の関数は必要に応じて実装
// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
// 頂点属性の for_each
void for_each(int u, int v, function<void(int, int)> f) {
if (vid[u] > vid[v]) swap(u, v);
f(max(vid[head[v]], vid[u]), vid[v]);
if (head[u] != head[v]) for_each(u, parent[head[v]], f);
}
// 頂点属性の for_each （有向
// fの3番目の引数には順方向なら0、逆方向なら1が渡される
void for_each_directed(int u, int v, function<void(int, int, int)> f) {
if (vid[u] > vid[v]) {
f(max(vid[head[u]], vid[v]), vid[u], 1);
if (head[u] != head[v]) for_each_directed(parent[head[u]], v, f);
}
else {
f(max(vid[head[v]], vid[u]), vid[v], 0);
if (head[u] != head[v]) for_each_directed(u, parent[head[v]], f);
}
}
// 辺属性の for_each
void for_each_edge(int u, int v, function<void(int, int)> f) {
if (vid[u] > vid[v]) swap(u, v);
if (head[u] != head[v]) {
f(vid[head[v]], vid[v]);
for_each_edge(u, parent[head[v]], f);
}
else {
if (u != v) f(vid[u] + 1, vid[v]);
}
}
// 頂点 u の d 個上の頂点を求める（存在しないなら0を返す）
int ancestor(int u, int d) {
while (true) {
if (depth[head[u]] > depth[u] - d) {
d -= depth[u] - depth[head[u]] + 1;
if (head[u] == 0) return 0;
u = parent[head[u]];
}
else {
return inv[vid[u] - d];
}
}
}
// 頂点 u と頂点 v の LCA を求める
int lca(int u, int v) {
if (vid[u] > vid[v]) swap(u, v);
if (head[u] == head[v]) return u;
return lca(u, parent[head[v]]);
}
// 頂点 u と頂点 v の距離を求める
int distance(int u, int v) {
return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}
};
//-----------------------------------------------------------------------------------
int N;
//-----------------------------------------------------------------------------------
int main() {
cin >> N;
HLDecomposition hld(N);
rep(i, 0, N - 1) {
int a, b; scanf("%d%d", &a, &b); a--; b--;
hld.add(a, b);
}
hld.build();
LazySegTreeAddSetSum st(N);
st.add(0, N - 1, 1);
int Q; cin >> Q;
ll ans = 0;
rep(q, 0, Q) {
int a, b; scanf("%d%d", &a, &b); a--; b--;
hld.for_each(a, b, [&](int u, int v) {
ans += st.query(u, v);
st.add(u, v, 1);
});
}
cout << ans << endl;
}