#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb push_back
const int MX = 1e5 + 5;
const int mod = 998244353;
int n, m, q;
int a[MX], b[MX];
int p[MX], c[MX];
int s[MX], t[MX], x[MX], y[MX];
int l[MX], r[MX], mid[MX], ans[MX];
int pos[MX], sz[MX], d[MX];
int hld_pa[MX], pa[MX];
ll tree[4 * MX], nm[4 * MX];
int cnt, num;
vector<int> adj[MX], h[MX];
vector<pair<int, int>> cst;
void dfs(int u, int pre) {
pa[u] = pre;
sz[u] = 1;
int mx = 0;
for(int i = 0; i < (int)adj[u].size(); i++) {
if(adj[u][i] == pre) continue;
d[adj[u][i]] = d[u] + 1;
dfs(adj[u][i], u);
mx = max(mx, sz[adj[u][i]]);
sz[u] += sz[adj[u][i]];
}
for(int i = 0; i < (int)adj[u].size(); i++) {
if(adj[u][i] == pre) continue;
if(sz[adj[u][i]] == mx) {
swap(adj[u][i], adj[u][0]);
break;
}
}
}
void hld(int u) {
pos[u] = num;
num++;
for(int i = 0; i < (int)adj[u].size(); i++) {
if(d[adj[u][i]] < d[u]) continue;
if(!i) hld_pa[adj[u][i]] = hld_pa[u];
else hld_pa[adj[u][i]] = adj[u][i];
}
for(int i = 0; i < (int)adj[u].size(); i++) {
if(d[adj[u][i]] < d[u]) continue;
hld(adj[u][i]);
}
}
void update(int id, int l, int r, int pos, int x) {
tree[id] += x;
nm[id]++;
if(l == r) return;
int mid = (l + r) / 2;
if(mid < pos) update(id * 2 + 2, mid + 1, r, pos, x);
else update(id * 2 + 1, l, mid, pos, x);
}
ll query(int id, int l, int r, int L, int R) {
if(L > r || l > R) return 0;
if(L <= l && r <= R) return tree[id];
int mid = (l + r) / 2;
return query(id * 2 + 1, l, mid, L, R) + query(id * 2 + 2, mid + 1, r, L, R);
}
int ch_p(int id, int l, int r, int L, int R) {
if(L > r || l > R) return 0;
if(L <= l && r <= R) return nm[id];
int mid = (l + r) / 2;
return ch_p(id * 2 + 1, l, mid, L, R) + ch_p(id * 2 + 2, mid + 1, r, L, R);
}
bool is;
ll find(int u, int v) {
if(hld_pa[u] == hld_pa[v]) {
if(u == v) return 0;
if(d[u] < d[v]) return query(0, 0, n - 1, pos[u] + 1, pos[v]);
else return query(0, 0, n - 1, pos[v] + 1, pos[u]);
}
if(d[hld_pa[u]] < d[hld_pa[v]]) return find(u, pa[hld_pa[v]]) + query(0, 0, n - 1, pos[hld_pa[v]], pos[v]);
else return find(pa[hld_pa[u]], v) + query(0, 0, n - 1, pos[hld_pa[u]], pos[u]);
}
int cnt_ch_p(int u, int v) {
if(hld_pa[u] == hld_pa[v]) {
if(u == v) return 0;
if(d[u] < d[v]) return ch_p(0, 0, n - 1, pos[u] + 1, pos[v]);
else return ch_p(0, 0, n - 1, pos[v] + 1, pos[u]);
}
if(d[hld_pa[u]] < d[hld_pa[v]]) return cnt_ch_p(u, pa[hld_pa[v]]) + ch_p(0, 0, n - 1, pos[hld_pa[v]], pos[v]);
else return cnt_ch_p(pa[hld_pa[u]], v) + ch_p(0, 0, n - 1, pos[hld_pa[u]], pos[u]);
}
void go() {
memset(tree, 0, sizeof(tree));
for(int i = 0; i < m; i++) {
update(0, 0, n - 1, pos[cst[i].ss], cst[i].ff);
for(int j = 0; j < (int)h[i].size(); j++) {
if(i == 1 && h[i][j] == 0) is = 1;
ll z = find(s[h[i][j]], t[h[i][j]]);
if(i == 1 && h[i][j] == 0) is = 0;
if(z > y[h[i][j]]) {
if(l[h[i][j]] == r[h[i][j]]) {
ans[h[i][j]] = i - 1;
cnt++;
}
else {
r[h[i][j]] = mid[h[i][j]];
mid[h[i][j]] = (r[h[i][j]] + l[h[i][j]]) / 2;
}
}
else {
if(l[h[i][j]] == r[h[i][j]]) {
ans[h[i][j]] = i;
cnt++;
}
else {
l[h[i][j]] = mid[h[i][j]] + 1;
mid[h[i][j]] = (r[h[i][j]] + l[h[i][j]]) / 2;
}
}
}
h[i].clear();
}
for(int i = 0; i < q; i++) {
if(ans[i]) continue;
h[mid[i]].pb(i);
}
}
void solve() {
for(int i = 0; i < q; i++) {
if(ans[i] >= 0) h[ans[i]].pb(i);
}
for(int i = 0; i < m; i++) {
update(0, 0, n - 1, pos[cst[i].ss], cst[i].ff);
for(int j = 0; j < (int)h[i].size(); j++) {
ans[h[i][j]] = cnt_ch_p(s[h[i][j]], t[h[i][j]]);
}
}
for(int i = 0; i < q; i++) {
ans[i] = cnt_ch_p(s[i], t[i]) - ans[i];
if(ans[i] > x[i]) ans[i] = -1;
else ans[i] = x[i] - ans[i];
}
}
int main() {
ios::sync_with_stdio(0);cin.tie(0);
cin >> n >> m >> q;
for(int i = 0; i < n - 1; i++) {
cin >> a[i] >> b[i];
a[i]--;
b[i]--;
adj[a[i]].pb(b[i]);
adj[b[i]].pb(a[i]);
}
dfs(0, 0);
hld(0);
for(int i = 0; i < m; i++) {
cin >> p[i] >> c[i];
p[i]--;
if(d[a[p[i]]] > d[b[p[i]]]) cst.pb({c[i], a[p[i]]});
else cst.pb({c[i], b[p[i]]});
}
sort(cst.begin(), cst.end());
for(int i = 0; i < q; i++) {
cin >> s[i] >> t[i] >> x[i] >> y[i];
s[i]--;
t[i]--;
l[i] = 0;
r[i] = m - 1;
mid[i] = r[i] / 2;
h[mid[i]].pb(i);
}
while(cnt < q) {
go();
}
solve();
for(int i = 0; i < q; i++) cout << ans[i] << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8148 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
8148 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
8148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8148 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
8748 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8148 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
8148 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
