#include <bits/stdc++.h>
using namespace std;
const int N = 1e5, M = 1e5, Q = 1e5;
typedef long long int lint;
int n, m, q;
struct edgePair{
int a, b;
vector<lint> t;
};
struct edge{
int v;
vector<lint> t;
};
struct SegTree{
int l, r;
lint tot, size;
SegTree* lChild;
SegTree* rChild;
SegTree(int l, int r){
this->l = l;
this->r = r;
tot = 0;
size = 0;
if (l+1 < r){
lChild = new SegTree(l, (r-l+1)/2+l);
rChild = new SegTree((r-l+1)/2+l, r);
}else {
lChild = NULL;
rChild = NULL;
}
}
SegTree(int l, int r, SegTree* lC, SegTree* rC){
this->l = l;
this->r = r;
lChild = lC;
rChild = rC;
if (lChild != NULL){
tot = lChild->tot+rChild->tot;
size = lChild->size + rChild->size;
}else {
tot = 0;
size = 0;
}
}
SegTree* add(int p, int v){
SegTree* n = new SegTree(l, r, lChild, rChild);
n->tot += v;
n->size ++;
if (lChild == NULL){
return n;
}else {
int m = (r-l+1)/2+l;
if (p < m){
n->lChild = lChild->add(p, v);
}else {
n->rChild = rChild->add(p, v);
}
}
return n;
}
};
edgePair edges[N];
map<lint, int> comp;
SegTree* trees[N];
vector<edge> con[N];
int binJump[N][20];
int dep[N];
int checks[M];
int pos[M];
void dfs(int i, int p){
binJump[i][0] = p;
for (edge e: con[i]){
if (e.v == p){
continue;
}
SegTree* nex = trees[i];
for (int x: e.t){
nex = nex->add(pos[x], checks[x]);
}
dep[e.v] = dep[i]+1;
trees[e.v] = nex;
dfs(e.v, i);
}
}
void calcBinJump(){
for (int x = 1; x < 20; x ++){
for (int i = 0; i < n; i ++){
binJump[x][i] = binJump[binJump[x][i-1]][i-1];
}
}
}
int lca(int a, int b){
int dif = dep[a]-dep[b];
while (dif > 0){
int i = 31-__builtin_ctz(dif);
a = binJump[a][i];
dif = dep[a]-dep[b];
}
swap(a, b);
dif = dep[a]-dep[b];
while (dif > 0){
int i = 31-__builtin_ctz(dif);
a = binJump[a][i];
dif = dep[a]-dep[b];
}
while (a != b){
int i = 0;
for (; i < 20; i ++){
if (binJump[a][i] == binJump[b][i]){
break;
}
}
i = max(0, i-1);
a = binJump[a][i];
b = binJump[b][i];
}
return a;
}
lint minGold(int s, int t, int a , lint Y){
SegTree *sP = trees[s], *tP = trees[t], *aP = trees[a];
lint notReq = 0, req = sP->size + tP->size - 2*aP->size;
// cout << "HI" << endl;
while (true){
if (sP->lChild == NULL){
lint v = sP->tot + tP->tot - 2*aP->tot;
if (v > Y){
}else {
notReq += sP->size + tP->size - 2*aP->size;
Y -= v;
}
break;
}
// printf("%d, %d, %d, %d, %d, %d \n", sP->l, sP->r, tP->l, tP->r, aP->l, aP->r);
lint v = sP->lChild->tot + tP->lChild->tot - 2*aP->lChild->tot;
if (v > Y){
sP = sP->lChild;
tP = tP->lChild;
aP = aP->lChild;
}else {
notReq += sP->lChild->size + tP->lChild->size - 2*aP->lChild->size;
sP = sP->rChild;
tP = tP->rChild;
aP = aP->rChild;
Y -= v;
}
}
return req-notReq;
}
int main(){
cin >> n >> m >> q;
for (int x = 0; x < n-1; x ++){
int a, b;
cin >> a >> b;
a --, b --;
edges[x] = {a, b, {}};
}
// cout << "HI" << endl;
vector<pair<int, int>> vals;
for (int x = 0; x < m; x ++){
lint p, v;
cin >> p >> v;
p --;
checks[x] = v;
vals.push_back({v, x});
edges[p].t.push_back(x);
}
sort(vals.begin(), vals.end());
// cout << "HI" << endl;
for (int x = 0; x < m; x ++){
pos[vals[x].second] = x;
}
for (int x = 0; x < n-1; x ++){
int a = edges[x].a, b = edges[x].b;
con[a].push_back({b, edges[x].t});
con[b].push_back({a, edges[x].t});
}
// cout << "HI" << endl;
trees[0] = new SegTree(0, m);
dfs(0, 0);
calcBinJump();
// cout << "HI" << endl;
for (int x = 0; x < q; x ++){
lint s, d, X, Y;
cin >> s >> d >> X >> Y;
s --, d --;
lint a = lca(s, d);
// cout << x << endl;
cout << max(-1LL, X-minGold(s, d, a, Y)) << endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
9308 KB |
Output is correct |
| 2 |
Correct |
2 ms |
9308 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
9304 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
9308 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
11100 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
9308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
9308 KB |
Output is correct |
| 2 |
Correct |
2 ms |
9308 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
9304 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
