結果
| 問題 |
No.399 動的な領主
|
| コンテスト | |
| ユーザー |
 mdj982
|
| 提出日時 | 2020-01-08 22:36:30 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 487 ms / 2,000 ms |
| コード長 | 16,836 bytes |
| コンパイル時間 | 2,887 ms |
| コンパイル使用メモリ | 234,200 KB |
| 最終ジャッジ日時 | 2025-01-08 16:58:21 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 19 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using ll = long long int;
using vll = vector<ll>; using vvll = vector<vll>; using vvvll = vector<vvll>;
using vd = vector<double>; using vvd = vector<vd>; using vvvd = vector<vvd>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using cdouble = complex<double>;
const double eps = 1e-7;
#define Loop(i, n) for(int i = 0; i < int(n); i++)
#define Loopll(i, n) for(ll i = 0; i < ll(n); i++)
#define Loop1(i, n) for(int i = 1; i <= int(n); i++)
#define Loopll1(i, n) for(ll i = 1; i <= ll(n); i++)
#define Loopr(i, n) for(int i = int(n) - 1; i >= 0; i--)
#define Looprll(i, n) for(ll i = ll(n) - 1; i >= 0; i--)
#define Loopr1(i, n) for(int i = int(n); i >= 1; i--)
#define Looprll1(i, n) for(ll i = ll(n); i >= 1; i--)
#define Foreach(buf, container) for(const auto &buf : container)
#define Foreachr(buf, container) for(const auto &buf : reversed(container))
#define Loopdiag(i, j, h, w, sum) for(int i = ((sum) >= (h) ? (h) - 1 : (sum)), j = (sum) - i; i >= 0 && j < (w); i--, j++)
#define Loopdiagr(i, j, h, w, sum) for(int j = ((sum) >= (w) ? (w) - 1 : (sum)), i = (sum) - j; j >= 0 && i < (h); j--, i++)
#define Loopdiagsym(i, j, h, w, gap) for (int i = ((gap) >= 0 ? (gap) : 0), j = i - (gap); i < (h) && j < (w); i++, j++)
#define Loopdiagsymr(i, j, h, w, gap) for (int i = ((gap) > (h) - (w) - 1 ? (h) - 1 : (w) - 1 + (gap)), j = i - (gap); i >= 0 && j >= 0; i--, j--)
#define Loopitr(itr, container) for(auto itr = container.begin(); itr != container.end(); itr++)
#define printv(vector) Loop(ex_i, vector.size()) { cout << vector[ex_i] << " "; } cout << endl;
#define printmx(matrix) Loop(ex_i, matrix.size()) { Loop(ex_j, matrix[ex_i].size()) { cout << matrix[ex_i][ex_j] << " "; } cout << endl; }
#define quickio() ios::sync_with_stdio(false); cin.tie(0);
#define bitmanip(m,val) static_cast<bitset<(int)m>>(val)
#define Comp(type_t) bool operator<(const type_t &another) const
#define fst first
#define snd second
#define INF INFINITY
bool feq(double x, double y) { return abs(x - y) <= eps; }
bool inrange(ll x, ll t) { return x >= 0 && x < t; }
bool inrange(vll xs, ll t) { Foreach(x, xs) if (!(x >= 0 && x < t)) return false; return true; }
int ceillog2(ll x) { return int(ceil(log2(x))); }
int floorlog2(ll x) { return int(floor(log2(x))); }
template<class T> T reversed(T container) { reverse(container.begin(), container.end()); return container; }
ll rndf(double x) { return (ll)(x + (x >= 0 ? 0.5 : -0.5)); }
ll floorsqrt(ll x) { ll m = (ll)sqrt((double)x); return m + (m * m <= x ? 0 : -1); }
ll ceilsqrt(ll x) { ll m = (ll)sqrt((double)x); return m + (x <= m * m ? 0 : 1); }
ll rnddiv(ll a, ll b) { return (a / b + (a % b * 2 >= b ? 1 : 0)); }
ll ceildiv(ll a, ll b) { return (a / b + (a % b == 0 ? 0 : 1)); }
ll gcd(ll m, ll n) { if (n == 0) return m; else return gcd(n, m % n); }
ll lcm(ll m, ll n) { return m * n / gcd(m, n); }
//========================================================================//
struct tree_t {
using nodeval_t = int;
using edgeval_t = int;
int n; // |V|, index begins with 0
vector<P> edges; // E
vector<nodeval_t> vals; // value of nodes
vector<edgeval_t> costs; // cost, distance, or weight of edges
};
// a should be sorted, return will be the root
template<class val_t, class tree_t>
int make_treap(const vector<val_t> &a, const tree_t &T, int l = 0, int r = -1, int p = -1) {
if (r == -1) { r = a.size(); T.n = a.size(); }
if (r - l == 0) return -1;
int mid = (l + r) / 2;
if (p != -1) T.edges.push_back({ mid, p });
make_treap(a, T, l, mid, mid);
make_treap(a, T, mid + 1, r, mid);
return mid;
}
#define ANCESTOR
#define HLD
class Tree {
using nodeval_t = int;
using edgeval_t = int;
private:
struct node {
vi childs; int parent = -1;
int deg = -1; // the number of edges of the path to the root
int eid = -1; // edge id of the edge connected by its parent and itself
int subtree_n = 1; // the number of nodes of the partial tree rooted by itself
#ifdef ANCESTOR
int visited = -1; // time stamp of visiting on DFS, call solve_sprs_ancestors() for activation
int departed = -1; // time stamp of departure on DFS, call solve_sprs_ancestors() for activation
#endif
#ifdef HLD
int pid = -1; // path id of heavy light decompotion
int qid = -1; // id in its path
#endif
nodeval_t val; // value of the node itself
edgeval_t cost; // cost of the edge connected by its parent and itself
};
struct edgeinfo_t {
int eid; int to; edgeval_t cost;
};
int n;
static const nodeval_t init_val = 0;
static const edgeval_t init_cost = 1;
#ifdef ANCESTOR
vvi sprs_ancestors; // (1 << j)-th ancestors in each node_id = i
#endif
#ifdef HLD
vvi hld_paths; // paths
#endif
void tree_construction(const vector<vector<edgeinfo_t>> &edges) {
leaves = {};
queue<int> que;
que.push(root);
while (que.size()) {
int a = que.front(); que.pop();
deg_order.push_back(a);
if (a == Tree::root) nodes[a].deg = 0;
int leaf_flag = true;
Loop(i, edges[a].size()) {
int b = edges[a][i].to;
if (nodes[b].deg != -1) {
nodes[a].parent = b;
nodes[a].eid = edges[a][i].eid;
nodes[a].cost = edges[a][i].cost;
nodes[a].deg = nodes[b].deg + 1;
}
else {
leaf_flag = false;
nodes[a].childs.push_back(b);
que.push(b);
}
}
if (leaf_flag) leaves.push_back(a);
}
Loopr(i, n) {
int a = deg_order[i];
Loop(j, nodes[a].childs.size()) {
int b = nodes[a].childs[j];
nodes[a].subtree_n += nodes[b].subtree_n;
}
}
}
public:
vector<node> nodes;
vi deg_order; // node ids, sorted by deg
vi leaves;
int root;
public:
// T should be non-empty tree
Tree(const tree_t &T, int root) {
this->n = T.n;
this->root = root;
nodes.resize(n);
Loop(i, n) {
nodes[i].val = (int)(T.vals.size()) > i ? T.vals[i] : init_val;
nodes[i].cost = init_cost;
}
vector<vector<edgeinfo_t>> edges(n);
Loop(i, n - 1) {
edges[T.edges[i].fst].push_back({ i, T.edges[i].snd, ((int)(T.costs.size()) > i ? T.costs[i] : init_cost) });
edges[T.edges[i].snd].push_back({ i, T.edges[i].fst, ((int)(T.costs.size()) > i ? T.costs[i] : init_cost) });
}
tree_construction(edges);
return;
}
int solve_diameter() {
vi d(n, -1);
queue<int> que;
d[deg_order[n - 1]] = 0;
que.push(deg_order[n - 1]);
while (que.size()) {
int a = que.front(); que.pop();
int p = nodes[a].parent;
if (d[p] == -1) {
d[p] = d[a] + 1;
que.push(nodes[a].parent);
}
Foreach(b, nodes[a].childs) {
if (d[b] == -1) {
d[b] = d[a] + 1;
que.push(b);
}
}
}
return *max_element(d.begin(), d.end());
}
pair<int, vi> solve_center_of_gravity() {
pair<int, vi> ret = { INT_MAX,{} };
vi record(n, 1);
Foreach(a, deg_order) {
int x = n - 1, max_x = INT_MIN;
Foreach(b, nodes[a].childs) {
max_x = max(max_x, record[b]);
x -= record[b];
record[a] += record[b];
}
max_x = max(max_x, x);
if (max_x < ret.fst) ret = { max_x,{ a } };
else if (max_x == ret.fst) ret.snd.push_back(a);
}
sort(ret.snd.begin(), ret.snd.end());
return ret;
}
vi solve_node_inclusion_cnt_in_all_path(bool enable_single_node_path) {
vi ret(n, 0);
Loop(i, n) {
int a = i;
// desendants to desendants
Foreach(b, nodes[a].childs) {
ret[i] += nodes[b].subtree_n * (nodes[a].subtree_n - nodes[b].subtree_n - 1);
}
ret[i] /= 2; // because of double counting
ret[i] += (nodes[a].subtree_n - 1) * (n - nodes[a].subtree_n); // desendants to the others except for itself
ret[i] += n - 1; // itself to the others
if (enable_single_node_path) ret[i]++; // itself
}
return ret;
}
vi solve_edge_inclusion_cnt_in_all_path() {
vi ret(n - 1, 0);
Loop(i, n) {
int eid = nodes[i].eid;
if (eid < 0) continue;
ret[eid] = nodes[i].subtree_n * (n - nodes[i].subtree_n); // members in the partial tree to the others
}
return ret;
}
#ifdef ANCESTOR
void solve_sprs_ancestors() {
sprs_ancestors.resize(n);
vector<int> current_ancestors;
stack<int> stk;
stk.push(Tree::root);
int time_stamp = 0;
while (stk.size()) {
int a = stk.top(); stk.pop();
nodes[a].visited = time_stamp++;
for (int i = 1; i <= (int)(current_ancestors.size()); i *= 2) {
sprs_ancestors[a].push_back(current_ancestors[current_ancestors.size() - i]);
}
if (nodes[a].childs.size()) {
Loop(i, nodes[a].childs.size()) {
stk.push(nodes[a].childs[i]);
}
current_ancestors.push_back(a);
}
else {
nodes[a].departed = time_stamp++;
while (current_ancestors.size() && (stk.empty() || nodes[stk.top()].parent != current_ancestors.back())) {
nodes[current_ancestors.back()].departed = time_stamp++;
current_ancestors.pop_back();
}
}
}
return;
}
bool is_ancestor(int descendant, int ancestor) {
return nodes[ancestor].visited < nodes[descendant].visited
&& nodes[descendant].departed < nodes[ancestor].departed;
}
int get_lowest_common_ancestor(int u, int v) {
if (u == v) return u;
if (is_ancestor(u, v)) return v;
if (is_ancestor(v, u)) return u;
int a = u;
while (!is_ancestor(v, sprs_ancestors[a][0])) {
int b = sprs_ancestors[a][0];
Loop1(i, sprs_ancestors[a].size() - 1) {
if (is_ancestor(v, sprs_ancestors[a][i])) break;
else b = sprs_ancestors[a][i - 1];
}
a = b;
}
return sprs_ancestors[a][0];
}
int get_ancestor(int descendant, int k) {
if (k == 0) return descendant;
int l = (int)log2(k);
if (l >= sprs_ancestors[descendant].size()) return -1;
else return get_ancestor(sprs_ancestors[descendant][l], k - (1 << l));
}
// return first value causing "t" in evalfunc that returns descendant->[f,...,f,t,...,t]->root
// NOTE: if [f,...,f] then return -1
template<typename bsargv_t>
int binary_search_upper_ancestor(int descendant, const bsargv_t &bsargv, bool(*evalfunc)(int, const bsargv_t&)) {
if (evalfunc(descendant, bsargv)) return descendant;
if (descendant == root) return -1;
Loop(i, sprs_ancestors[descendant].size()) {
if (evalfunc(sprs_ancestors[descendant][i], bsargv)) {
if (i == 0) return binary_search_upper_ancestor(sprs_ancestors[descendant][0], bsargv, evalfunc);
else return binary_search_upper_ancestor(sprs_ancestors[descendant][i - 1], bsargv, evalfunc);
}
}
return binary_search_upper_ancestor(sprs_ancestors[descendant].back(), bsargv, evalfunc);
}
// return last value causing "t" in evalfunc that returns descendant->[t,...,t,f,...,f]->root
// NOTE: if [f,...,f] then return -1
template<typename bsargv_t>
int binary_search_lower_ancestor(int descendant, const bsargv_t &bsargv, bool(*evalfunc)(int, const bsargv_t&)) {
if (!evalfunc(descendant, bsargv)) return -1;
if (descendant == root) return root;
Loop(i, sprs_ancestors[descendant].size()) {
if (!evalfunc(sprs_ancestors[descendant][i], bsargv)) {
if (i == 0) return descendant;
else return binary_search_lower_ancestor(sprs_ancestors[descendant][i - 1], bsargv, evalfunc);
}
}
return binary_search_lower_ancestor(sprs_ancestors[descendant].back(), bsargv, evalfunc);
}
// static bool evalfunc(int id, bsargv_t bsargv);
#endif
#ifdef HLD
void solve_hld() {
Foreach(a, deg_order) {
if (nodes[a].pid == -1) {
nodes[a].pid = int(hld_paths.size());
nodes[a].qid = 0;
hld_paths.push_back({ a });
}
int max_id = -1;
int max_subtree_n = 0;
Foreach(b, nodes[a].childs) {
if (nodes[b].subtree_n > max_subtree_n) {
max_id = b;
max_subtree_n = nodes[b].subtree_n;
}
}
if (max_id == -1) continue;
nodes[max_id].pid = nodes[a].pid;
nodes[max_id].qid = nodes[a].qid + 1;
hld_paths[nodes[a].pid].push_back(max_id);
}
}
struct pathinfo_t {
int id;
int l, r; // [l, r)
};
// return all node ids in the single path
vector<int> get_ids_in_path(const pathinfo_t &pathinfo) {
vi ret(pathinfo.r - pathinfo.l);
Loop(i, ret.size()) {
ret[i] = hld_paths[pathinfo.id][pathinfo.l + i];
}
return ret;
}
// if weight is for each node, include_lca = true
// if weight is for each edge, include_lca = false
vector<pathinfo_t> get_path_in_hld(int u, int v, bool include_lca) {
vector<pathinfo_t> ret;
int w = get_lowest_common_ancestor(u, v);
Foreach(x, vector<int>({ u, v })) {
int a = x;
while (a != w) {
if (nodes[a].pid != nodes[w].pid) {
ret.push_back({ nodes[a].pid, 0, nodes[a].qid + 1 });
a = nodes[hld_paths[nodes[a].pid][0]].parent;
}
else {
ret.push_back({ nodes[a].pid, nodes[w].qid + 1, nodes[a].qid + 1 });
a = w;
}
}
}
if (include_lca) {
Loop(i, ret.size()) {
if (nodes[w].pid == ret[i].id) {
ret[i].l -= 1;
include_lca = false;
}
}
}
if (include_lca) {
ret.push_back({ nodes[w].pid, nodes[w].qid, nodes[w].qid + 1 });
}
return ret;
}
vi get_hld_path_sizes() {
vi ret(hld_paths.size());
Loop(i, hld_paths.size()) {
ret[i] = int(hld_paths[i].size());
}
return ret;
}
int get_hld_path_size(int pid) {
return int(hld_paths[pid].size());
}
#endif
};
class SegTreeSum {
using val_t = ll;
private:
struct segval_t {
bool enable;
val_t upd, add, sum;
};
int n, N; // n is the original size, while N is the extended size
int base;
vector<segval_t> nodes;
vi idl, idr, cover_size;
void merge(int id) {
nodes[id].sum = nodes[idl[id]].sum + nodes[idl[id]].add * cover_size[idl[id]]
+ nodes[idr[id]].sum + nodes[idr[id]].add * cover_size[idr[id]];
}
void lazy(int id) {
if (id >= base) return;
if (nodes[id].enable) {
val_t upd = nodes[id].upd + nodes[id].add;
nodes[idl[id]] = { true, upd, 0, upd * cover_size[idl[id]] };
nodes[idr[id]] = { true, upd, 0, upd * cover_size[idr[id]] };
nodes[id] = { false, 0, 0, upd * cover_size[id] };
}
else {
nodes[idl[id]].add += nodes[id].add;
nodes[idr[id]].add += nodes[id].add;
nodes[id].add = 0;
merge(id);
}
}
enum change_t {
UPD, ADD
};
void change_rec(int s, int t, int l, int r, int id, val_t x, change_t op) {
if (s == l && t == r) {
if (op == UPD) nodes[id] = { true, x, 0, x * cover_size[id] };
if (op == ADD) nodes[id].add += x;
}
else {
lazy(id);
int m = (l + r) >> 1;
if (s < m && m < t) {
change_rec(s, m, l, m, idl[id], x, op);
change_rec(m, t, m, r, idr[id], x, op);
}
else if (s < m) {
change_rec(s, t, l, m, idl[id], x, op);
}
else if (m < t) {
change_rec(s, t, m, r, idr[id], x, op);
}
merge(id);
}
}
val_t solve_rec(int s, int t, int l, int r, int id) {
val_t v = 0;
if (s == l && t == r) {
v = nodes[id].sum;
}
else {
lazy(id);
int m = (l + r) >> 1;
if (s < m && m < t) {
val_t v0 = solve_rec(s, m, l, m, idl[id]);
val_t v1 = solve_rec(m, t, m, r, idr[id]);
v = v0 + v1;
}
else if (s < m) {
v = solve_rec(s, t, l, m, idl[id]);
}
else if (m < t) {
v = solve_rec(s, t, m, r, idr[id]);
}
}
v += nodes[id].add * (t - s);
return v;
}
void common_init() {
idl.resize(base + N, -1);
idr.resize(base + N, -1);
Loop(i, base) {
idl[i] = (i << 1) + 1;
idr[i] = (i << 1) + 2;
}
cover_size.resize(base + N);
Loop(i, n) {
cover_size[base + i] = 1;
}
Loopr(i, base) {
cover_size[i] = cover_size[idl[i]] + cover_size[idr[i]];
}
}
public:
SegTreeSum(int n, val_t init = 0) {
this->n = n;
N = 1 << ceillog2(n);
base = N - 1;
nodes = vector<segval_t>(base + N, { false, 0, 0, 0 });
common_init();
upd(0, n, init);
}
SegTreeSum(const vector<val_t> &a) {
this->n = int(a.size());
N = 1 << ceillog2(n);
base = N - 1;
nodes = vector<segval_t>(base + N, { false, 0, 0, 0 });
common_init();
Loop(i, n) {
nodes[base + i] = { true, a[i], 0, a[i] };
}
Loopr(i, base) {
merge(i);
}
}
void upd(int s, int t, val_t x) {
if (s >= t) return;
change_rec(s, t, 0, N, 0, x, UPD);
}
void add(int s, int t, val_t x) {
if (s >= t) return;
change_rec(s, t, 0, N, 0, x, ADD);
}
val_t sumof(int s, int t) {
if (s >= t) return 0;
return solve_rec(s, t, 0, N, 0);
}
};
int main() {
quickio();
tree_t T; cin >> T.n;
Loop(i, T.n - 1) {
int s, t; cin >> s >> t; s--; t--;
T.edges.push_back({ s, t });
}
Tree *tree = new Tree(T, 0);
tree->solve_sprs_ancestors();
tree->solve_hld();
vi ss = tree->get_hld_path_sizes();
vector<SegTreeSum*> sts(ss.size());
Loop(i, ss.size()) {
sts[i] = new SegTreeSum(ss[i]);
}
int q; cin >> q;
Loop(_, q) {
int s, t; cin >> s >> t; s--; t--;
auto pathinfos = tree->get_path_in_hld(s, t, true);
Foreach(pathinfo, pathinfos) {
sts[pathinfo.id]->add(pathinfo.l, pathinfo.r, 1);
}
}
ll ans = 0;
Loop(i, ss.size()) {
Loop(j, ss[i]) {
ll x = sts[i]->sumof(j, j + 1);
ans += (x * (x + 1)) >> 1;
}
}
cout << ans << endl;
}