#include <bits/stdc++.h>
using namespace std;
using p = pair<int, int>;
const int MAX_N = 100005;
int n, m, q, id=1, len=131072, ids[MAX_N], sz[MAX_N], depth[MAX_N] = {0};
long long tree[262144];
vector<int> paths[MAX_N];
vector<p> pathsA;
int table[17][MAX_N];
int LCA(int a, int b) {
if(depth[a] != depth[b]) {
if(depth[a] < depth[b]) swap(a, b);
int diff = depth[a] - depth[b];
for(int i = 16; i >= 0; i --) {
if(diff & (1 << i)) {
a = table[i][a];
}
}
}
for(int i = 16; i > 0; i --) {
if(table[i][a] != table[i][b]) {
a = table[i][a];
b = table[i][b];
}
}
if(a != b) a = table[0][a];
return a;
}
void calcTable() {
for(int i = 1; i < 17; i ++) {
for(int j = 1; j <= n; j ++) {
table[i][j] = table[i - 1][table[i - 1][j]];
}
}
}
void dfs(int cur=1, int prev=-1) {
ids[cur] = id ++;
sz[cur] = 1;
for(int i: paths[cur]) {
if(i == prev) continue;
table[0][i] = cur;
depth[i] = depth[cur] + 1;
dfs(i, cur);
sz[cur] += sz[i];
}
}
void update(int a, int v) {
a += len;
tree[a] += v;
for(a /= 2; a >= 1; a /= 2) {
tree[a] = tree[a * 2] + tree[a * 2 + 1];
}
}
void rangeUpdate(int a, int v) {
int b = ids[a] + sz[a];
a = ids[a];
update(a, v);
update(b, -v);
}
long long query(int a, int b) {
a += len;
b += len;
long long tot = 0;
for(; a <= b; a /= 2, b /= 2) {
if(a & 1) {
tot += tree[a ++];
}
if(!(b & 1)) {
tot += tree[b --];
}
}
return tot;
}
long long query(int b) {
int a = 0;
b = ids[b];
return query(a, b);
}
vector<p> sts, lh;
vector<int> ans, cnts, mids[MAX_N];
struct N {
int a, b, c;
long long g, s;
N() {}
};
vector<N> qs;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> q;
for(int i = 1; i < n; i ++) {
int a, b;
cin >> a >> b;
paths[a].push_back(b);
paths[b].push_back(a);
pathsA.push_back({a, b});
}
dfs(); calcTable();
sts.resize(m);
for(int i = 0; i < m; i ++) {
cin >> sts[i].second >> sts[i].first;
sts[i].second --;
sts[i].second = depth[pathsA[sts[i].second].first] > depth[pathsA[sts[i].second].second] ? pathsA[sts[i].second].first : pathsA[sts[i].second].second;
}
sort(sts.begin(), sts.end());
qs.resize(q); ans.resize(q); lh.resize(q); cnts.resize(q);
for(int i = 0; i < q; i ++) {
cin >> qs[i].a >> qs[i].b >> qs[i].g >> qs[i].s;
qs[i].c = LCA(qs[i].a, qs[i].b);
lh[i] = {0, m - 1};
ans[i] = -1;
}
while(1) {
bool emp = true;
for(int i = 0; i < q; i ++) {
auto&[low, high] = lh[i];
if(low > high) continue;
emp = false;
mids[(low + high) >> 1].push_back(i);
}
for(auto&i: tree) i = 0;
for(int l = 0; l < m; l ++) {
auto&[C, P] = sts[l];
rangeUpdate(P, emp ? 1 : C);
for(auto i: mids[l]) {
N& q = qs[i];
long long cs = query(q.a) + query(q.b) - query(q.c) * 2;
auto&[low, high] = lh[i];
if(cs <= q.s) {
ans[i] = l;
low = l + 1;
} else {
high = l - 1;
}
}
mids[l].clear();
}
if(emp) {
for(int i = 0; i < q; i ++) {
N& q = qs[i];
cnts[i] = (int)(query(q.a) + query(q.b) - query(q.c) * 2);
if(ans[i] >= 0) mids[ans[i]].push_back(i);
}
for(auto&i: tree) i = 0;
break;
}
}
for(int l = 0; l < m; l ++) {
auto&[C, P] = sts[l];
rangeUpdate(P, 1);
for(auto i: mids[l]) {
N& q = qs[i];
int cs = (int)(query(q.a) + query(q.b) - query(q.c) * 2);
cnts[i] -= cs;
}
}
for(int i = 0; i < q; i ++) {
if(cnts[i] <= qs[i].g) cout << qs[i].g - cnts[i] << "\n";
else cout << "-1\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
14936 KB |
Output is correct |
| 2 |
Correct |
3 ms |
14940 KB |
Output is correct |
| 3 |
Correct |
3 ms |
14940 KB |
Output is correct |
| 4 |
Correct |
3 ms |
14940 KB |
Output is correct |
| 5 |
Incorrect |
8 ms |
15192 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14940 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
15416 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
14940 KB |
Output is correct |
| 2 |
Correct |
11 ms |
15452 KB |
Output is correct |
| 3 |
Correct |
11 ms |
15408 KB |
Output is correct |
| 4 |
Correct |
12 ms |
15516 KB |
Output is correct |
| 5 |
Correct |
527 ms |
40436 KB |
Output is correct |
| 6 |
Correct |
513 ms |
40308 KB |
Output is correct |
| 7 |
Correct |
708 ms |
40484 KB |
Output is correct |
| 8 |
Correct |
851 ms |
48516 KB |
Output is correct |
| 9 |
Correct |
834 ms |
48324 KB |
Output is correct |
| 10 |
Correct |
847 ms |
48520 KB |
Output is correct |
| 11 |
Correct |
697 ms |
48320 KB |
Output is correct |
| 12 |
Correct |
687 ms |
48328 KB |
Output is correct |
| 13 |
Correct |
669 ms |
48372 KB |
Output is correct |
| 14 |
Correct |
457 ms |
47748 KB |
Output is correct |
| 15 |
Correct |
453 ms |
47560 KB |
Output is correct |
| 16 |
Correct |
490 ms |
48052 KB |
Output is correct |
| 17 |
Correct |
491 ms |
47848 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
14936 KB |
Output is correct |
| 2 |
Correct |
3 ms |
14940 KB |
Output is correct |
| 3 |
Correct |
3 ms |
14940 KB |
Output is correct |
| 4 |
Correct |
3 ms |
14940 KB |
Output is correct |
| 5 |
Incorrect |
8 ms |
15192 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
