program_contest_library
This documentation is automatically generated by online-judge-tools/verification-helper
test/aoj2270.test.cpp
- category: test
-
View this file on GitHub
- Last commit date: 2020-04-08 17:56:23+09:00
- see: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2270
Depends on
Code
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2270"
#include "../memo/macro.hpp"
#include "../data_structure/BIT.cpp"
#include "../data_structure/Mo_tree_vertex.cpp"
signed main(void) {
ll n, q;
cin >> n >> q;
vector<ll> x(n);
REP(i, n) cin >> x[i];
vector<ll> vs(x);
sort(ALL(vs));
vs.erase(unique(ALL(vs)), vs.end());
REP(i, n) x[i] = lower_bound(ALL(vs), x[i]) - vs.begin();
BIT bit(vs.size());
auto add = [&](ll idx) { bit.update(x[idx], 1); };
auto del = [&](ll idx) { bit.update(x[idx], -1); };
Mo_Tree_Vertex mo(n, add, del);
REP(i, n-1) {
ll a, b;
cin >> a >> b;
a--, b--;
mo.add_edge(a, b);
}
mo.prepare();
vector<ll> k(q);
REP(i, q) {
ll a, b;
cin >> a >> b >> k[i];
a--, b--;
mo.insert(a, b);
}
mo.build();
vector<ll> ans(q);
REP(i, q) {
ll idx = mo.process();
ans[idx] = vs[bit.lower_bound(k[idx])];
}
REP(i, q) cout << ans[i] << "\n";
cout << flush;
return 0;
}
#line 1 "test/aoj2270.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2270"
#line 1 "memo/macro.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<ll, ll>;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;
const ll INF = 1LL<<60;
#line 1 "data_structure/BIT.cpp"
// BEGIN CUT
struct BIT {
int n;
vector<ll> bit;
BIT(int sz) {
n=1; while(n < sz) n*=2;
bit.assign(n+1, 0);
}
void update(int i, ll w) {
for(int x=i+1; x<(int)bit.size(); x += x&-x) bit[x] += w;
}
// [0,i]
ll query(int i) {
ll ret = 0;
for(int x=i+1; x>0; x -= x&-x) ret += bit[x];
return ret;
}
// 合計がw以上の最小の位置
int lower_bound(ll w) {
int x = 0;
for(int k=n; k>0; k>>=1) {
if(x+k <= n && bit[x+k] < w) {
w -= bit[x+k];
x += k;
}
}
return x;
}
};
// END CUT
#line 1 "data_structure/Mo_tree_vertex.cpp"
// BEGIN CUT
// 頂点クエリのMo
// HL分解で頂点クエリするときに下の辺に下ろすみたいなのをする
// add_edgeとinsertをした後buildをしてprocessを進めていく
struct Mo_Tree_Vertex {
vector<vector<int>> g, parent;
vector<int> vs, in;
vector<int> left, right, order, lca, dep;
vector<bool> v;
int width;
int nl, nr, ptr;
using F = function<void(int)>;
F add, del;
void dfs(int idx, int depth, int par) {
in[idx] = (int) vs.size();
dep[idx] = depth;
parent[0][idx] = par;
vs.push_back(idx);
for(auto &to : g[idx]) {
if(to == par) continue;
dfs(to, depth + 1, idx);
vs.push_back(to);
}
}
int getlca(int u, int v) {
if(dep[u] > dep[v]) swap(u, v);
for(int k = 0; k < (int)parent.size(); k++) {
if(((dep[v] - dep[u]) >> k) & 1) {
v = parent[k][v];
}
}
if(u == v) return (u);
for(int k = (int)parent.size()-1; k >= 0; k--) {
if(parent[k][u] != parent[k][v]) {
u = parent[k][u];
v = parent[k][v];
}
}
return (parent[0][u]);
}
inline void distribute(int vertex) {
v[vertex].flip();
if(v[vertex]) add(vertex);
else del(vertex);
}
Mo_Tree_Vertex(int n, F a, F d) : g(n), in(n), dep(n), v(n), width((int)sqrt(2*n-1)), nl(0), nr(0), ptr(0), add(a), del(d) {
const auto lg = (int) (log2(n) + 1);
parent.resize(lg, vector<int>(n));
vs.reserve(2*n-1);
}
void add_edge(int x, int y) {
g[x].push_back(y);
g[y].push_back(x);
}
void prepare() {
dfs(0, 0, -1);
for(int k = 0; k+1 < (int)parent.size(); k++) {
for(int i = 0; i < (int)parent[k].size(); i++) {
if(parent[k][i] == -1) parent[k + 1][i] = -1;
else parent[k + 1][i] = parent[k][parent[k][i]];
}
}
}
// パスx,yのクエリ
void insert(int x, int y) {
if(in[x] > in[y]) swap(x, y);
left.push_back(in[x] + 1);
right.push_back(in[y] + 1);
lca.push_back(getlca(x, y));
}
void build() {
order.resize(left.size());
iota(begin(order), end(order), 0);
sort(begin(order), end(order), [&](int a, int b) {
if(left[a] / width != left[b] / width) return left[a] < left[b];
return bool((right[a] < right[b]) ^ (left[a] / width % 2));
});
}
int process() {
if(ptr == (int)order.size()) return (-1);
if(ptr > 0) distribute(lca[order[ptr - 1]]); // 前のクエリで追加したLCAを削除
const auto id = order[ptr];
while(nl > left[id]) distribute(vs[--nl]);
while(nr < right[id]) distribute(vs[nr++]);
while(nl < left[id]) distribute(vs[nl++]);
while(nr > right[id]) distribute(vs[--nr]);
distribute(lca[id]); // LCA の頂点を例外として追加する
return (order[ptr++]);
}
};
// END CUT
#line 5 "test/aoj2270.test.cpp"
signed main(void) {
ll n, q;
cin >> n >> q;
vector<ll> x(n);
REP(i, n) cin >> x[i];
vector<ll> vs(x);
sort(ALL(vs));
vs.erase(unique(ALL(vs)), vs.end());
REP(i, n) x[i] = lower_bound(ALL(vs), x[i]) - vs.begin();
BIT bit(vs.size());
auto add = [&](ll idx) { bit.update(x[idx], 1); };
auto del = [&](ll idx) { bit.update(x[idx], -1); };
Mo_Tree_Vertex mo(n, add, del);
REP(i, n-1) {
ll a, b;
cin >> a >> b;
a--, b--;
mo.add_edge(a, b);
}
mo.prepare();
vector<ll> k(q);
REP(i, q) {
ll a, b;
cin >> a >> b >> k[i];
a--, b--;
mo.insert(a, b);
}
mo.build();
vector<ll> ans(q);
REP(i, q) {
ll idx = mo.process();
ans[idx] = vs[bit.lower_bound(k[idx])];
}
REP(i, q) cout << ans[i] << "\n";
cout << flush;
return 0;
}