結果
| 問題 |
No.399 動的な領主
|
| コンテスト | |
| ユーザー |
 Astral__
|
| 提出日時 | 2024-02-29 21:22:06 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,628 bytes |
| コンパイル時間 | 3,451 ms |
| コンパイル使用メモリ | 273,364 KB |
| 実行使用メモリ | 26,624 KB |
| 最終ジャッジ日時 | 2024-09-29 12:58:17 |
| 合計ジャッジ時間 | 10,052 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 8 WA * 11 |
ソースコード
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
template<typename X, typename E>
struct LazySegTree {
using FX = function<X(X, E, long long)>;//Xに作用素Mを作用させる
int n;
int siz;
FX fx;
vector<X> dat;
vector<E> lazy;
LazySegTree(){}
LazySegTree(int _siz, FX _fx) : siz(_siz), fx(_fx) {
n = 1;
while(n < siz) n <<= 1;
dat.assign(n * 2, X::ide());
lazy.assign(n * 2, E::ide());
}
private:
void eval(int k, int len) {
if(lazy[k] == E::ide()) return;
if(k < n) {
lazy[k<<1] = op(lazy[k<<1], lazy[k]);
lazy[k<<1|1] = op(lazy[k<<1|1], lazy[k]);
}
dat[k] = fx(dat[k], lazy[k], len);
lazy[k] = E::ide();
}
X query(int a, int b, int l, int r, int k) {
eval(k,r-l);
if(r <= a || b <= l) return X::ide();
if(a <= l && r <= b) return dat[k];
int mid = (l + r)>>1;
X L = query(a, b, l, mid, k<<1);
X R = query(a, b, mid, r, k<<1|1);
return op(L, R);
}
void update(int a, int b, E m, int l, int r, int k) {//[a, b) := クエリ区間 [l, r) := 今見ている区間
eval(k, r-l);
if(r <= a || b <= l) return;
if(a <= l && r <= b) {
lazy[k] = op(lazy[k], m);
eval(k, r-l);
}
else {
int mid = (l + r)>>1;
update(a, b, m, l, mid, k<<1);
update(a, b, m, mid, r, k<<1|1);
dat[k] = op(dat[k<<1], dat[k<<1|1]);
}
}
public:
void set(int i, X x) {
dat[i + n - 1] = x;
}
void init() {
for(int i = n-1; i >= 1; i--) {
dat[i] = op(dat[i*2], dat[i * 2 + 1]);
}
}
void change(int l, int r, E m) {
update(l, r + 1, m, 1, n + 1, 1);
}
X get(int l, int r) {
return query(l, r + 1, 1, n + 1, 1);
}
void dump() {
for(int i = 1; i <= siz; i++) {
cout << get(i, i) << " ";//適宜直す。
}
cout << endl;
}
};
template <typename X, typename E>
struct HLD {
vector<int> siz;//[元の頂点番号] = サイズ
vector<int> num;//[元の頂点番号] = 振り直した頂点番号
vector<int> numrev;
vector<int> out;//[元の頂点番号] = new 半開区間で、その頂点を出た時の値 + 1
vector<int> par;//[振られた] = 振られた 自分の親
vector<int> head;//[振られた番号] = 振られた番号 自分の連結成分の頭
LazySegTree<X, E> seg;
using FX = function<X(X, E, long long)>;
FX fx;
int N;
int size = 1;
HLD(int _N, vector<vector<int>>& G, FX _fx) : N(_N), fx(_fx) {
par.resize(N+1);
iota(par.begin(), par.end(), 0);
siz.resize(N+1, 1);
num.assign(N+1, -1);
numrev.resize(N+1, -1);
out.resize(N+1, -1);
head.resize(N+1);
seg = LazySegTree<X, E>(N, fx);
auto dfs_siz = [&](auto f, int now, int prev) -> void {
int sum = 1;
for(int to : G[now]) {
if(to == prev) continue;
f(f, to, now);
sum += siz[to];
}
siz[now] = sum;
return;
};
dfs_siz(dfs_siz, 1, -1);
for(int i = 1; i <= N; i++) {
sort(G[i].begin(), G[i].end(), [&](int a, int b) {
return siz[a] > siz[b];
});
}
int idx = 1;
auto dfs_bunkai = [&](auto f, int now, int prev, int hed) -> void {
num[now] = idx;//番号付
numrev[idx] = now;
idx++;
par[num[now]] = prev;//親の頂点 //1だけは直前も自分も1
if(hed == -1)hed = num[now];
head[num[now]] = hed;
bool flag = true;
for(int i = 0; i <= int(G[now].size()) - 1; i++) {
if(num[G[now][i]] != -1) continue;
if(flag) f(f, G[now][i], num[now], hed), flag = false;
else f(f, G[now][i], num[now], -1);
}
out[now] = idx;
return;
};
dfs_bunkai(dfs_bunkai, 1, 1, -1);
}
private:
X get__(int u, int v) {
int w = num[getLCA(u, v)];//lcaで左右に分ける
u = num[u];
v = num[v];
X L = X::ide(), R = X::ide();
while(u != w) {
int hed = max<int>(head[u], w+1);//wまで登ると、wを左右で2回カウントしてしまう。
L = op(seg.get(hed, u), L); //根から上の方へ
if(hed != w) u = par[hed];
else u = w;
}
L = op(seg.get(w, w), L);//根から上の方へ
while(v != w) {
int hed = max<int>(head[v], w+1);
R = op(seg.get(hed, v), R); //根から上の方へ
if(hed != w) v = par[hed];
else v = w;
}
return op(L, R);//交換則を要する時はこの行を変更する必要があるかもしれない : 無いと思うがr
}
void change__(int u, int v, E e) {
int w = num[getLCA(u, v)];//lcaで左右に分ける
u = num[u];
v = num[v];
while(u != w) {
int hed = max<int>(head[u], w+1);//wまで登ると、wを左右で2回カウントしてしまう。
seg.change(hed, u, e); //根から上の方へ
if(hed != w) u = par[hed];
else u = w;
}
seg.change(w, w, e);
while(v != w) {
int hed = max<int>(head[v], w+1);
seg.change(hed, v, e);
if(hed != w) v = par[hed];
else v = w;
}
}
public:
void set(int pos, X x) {
pos = num[pos];
seg.set(pos, x);
}
void init() {
seg.init();
}
void change(int u, int v, E e) {
change__(u, v, e);
}
X get(int u, int v) {
return get__(u, v);
}
X subtree(int v) {
int l = num[v];
int r = out[v] - 1;
return seg.get(l, r);
}
int getLCA(int a, int b) {//入 : 元番号 出 : 元番号
a = num[a];
b = num[b];
while(true) {
if(a > b) swap(a, b);
if(head[a] == head[b]) return numrev[a];
b = par[head[b]];
}
}
int parent(int a) {//入 : 元番号
return numrev[par[num[a]]];
}
/*
Brief hld。
HLD<Monoid> hld(N, G) N...max_n G ... graph
パスに対するクエリがlog^2
部分木に対するクエリがlog
*/
};
struct Monoid {
ll a;
Monoid(){}
Monoid(ll _a) : a(_a) {
}
friend Monoid op(const Monoid& l, const Monoid& r) {
return l.a + r.a;
}
static Monoid ide() {
return 0LL;
}
bool operator==(const Monoid& x) const {return a == x.a;}
bool operator!=(const Monoid& x) const {return !(*this == x);}
};
struct E {
ll a;
E(){}
E(ll _a) : a(_a) {}
friend E op(const E& l, const E& r) {//rのが新しい。(affine)
return l.a + r.a;
}
static E ide() {
return 0LL;
}
bool operator==(const E& x) const {return (a == x.a);}
bool operator!=(const E& x) const {return !(*this == x);}
};
Monoid fx(const Monoid& l, const E& r, long long len) {
return l.a + r.a * len;
}
int main() {
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
cout << fixed << setprecision(15);
int N;
cin >> N;
vector<vector<int>> G(N+1);
for(int i = 1; i < N; i++) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
HLD<Monoid, E> hld(N, G, fx);
for(int i = 1; i <= N; i++) hld.set(i, 1);
hld.init();
int Q;
cin >> Q;
int ans = 0;
while(Q--) {
int a, b;
cin >> a >> b;
ans += hld.get(a, b).a;
hld.change(a, b, 1);
}
cout << ans << endl;
}