/// dwuy: _,\,,,_\,__,\,,_
#include <bits/stdc++.h>
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) int32_t(s.length())
#define MASK(k)(1LL<<(k))
#define TASK ""
#define int long long
using namespace std;
typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;
const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
pii operator + (const pii a, const pii b){ return {a.fi + b.fi, a.se + b.se}; }
struct Node{
bool f;
int sum, cnt;
Node *l, *r;
Node(int sum = 0, int cnt = 0){
this->f = 0;
this->sum = sum;
this->cnt = cnt;
this->l = this->r = NULL;
}
Node(Node *other){
this->cnt = other->cnt;
this->sum = other->sum;
this->l = other->l;
this->r = other->r;
}
};
struct persistent_SMT{
int n, m;
vector<Node*> root;
persistent_SMT(int n=0, int m=0){
this->n = n;
this->m = m;
this->root.assign(m+5, NULL);
root[0] = new Node();
}
void update(Node *cur, int l, int r, const int &pos, const int &val){
if(l==r){
cur->sum += val;
cur->cnt += val>0? 1 : -1;
return;
}
int mid = (l+r)>>1;
if(pos<=mid){
cur->l = cur->l? new Node(cur->l) : new Node();
update(cur->l, l, mid, pos, val);
cur->sum = cur->l->sum + (cur->r? cur->r->sum : 0);
cur->cnt = cur->l->cnt + (cur->r? cur->r->cnt : 0);
}
else{
cur->r = cur->r? new Node(cur->r) : new Node();
update(cur->r, mid+1, r, pos, val);
cur->sum = cur->r->sum + (cur->l? cur->l->sum : 0);
cur->cnt = cur->r->cnt + (cur->l? cur->l->cnt : 0);
}
}
void update(int pos, int val, int id){
if(root[id] == NULL) root[id] = new Node(root[id-1]);
update(root[id], 1, n, pos, val);
}
pii get(Node *cur, int l, int r, const int &pos){
if(l>pos || cur==NULL) return {0, 0};
if(r<=pos) return {cur->sum, cur->cnt};
int mid = (l+r)>>1;
return get(cur->l, l, mid, pos) + get(cur->r, mid+1, r, pos);
}
pii get(int pos, int id){
return get(root[id], 1, n, pos);
}
};
const int MX = 200005;
int n, m, q;
pii edges[MX];
pii weight[MX];
vector<int> G[MX];
void nhap(){
cin >> n >> m >> q;
for(int i=1; i<n; i++){
int u, v;
cin >> u >> v;
edges[i] = {u, v};
G[u].push_back(v);
G[v].push_back(u);
}
int e = m;
for(int i=1, t=1; i<=m; i++){
int p, c;
cin >> p >> c;
weight[t] = {c, p};
if(c!=0) t++;
else e--;
}
m = e;
}
int dfsID = 0;
int h[MX];
int p[MX][17];
int num[MX];
int clo[MX];
void dfs(int u){
num[u] = ++dfsID;
h[u] = h[p[u][0]] + 1;
for(int v: G[u]){
if(v == p[u][0]) continue;
p[v][0] = u;
dfs(v);
}
clo[u] = dfsID;
}
int LCA(int u, int v){
if(h[u] > h[v]) swap(u, v);
for(int i=16; i>=0; i--) if(h[p[v][i]] >= h[u]) v = p[v][i];
if(u == v) return u;
for(int i=16; i>=0; i--) if(p[u][i] != p[v][i]){
u = p[u][i];
v = p[v][i];
}
return p[u][0];
}
void solve(){
dfs(1);
for(int j=1; j<=16; j++){
for(int i=1; i<=n; i++){
p[i][j] = p[p[i][j-1]][j-1];
}
}
persistent_SMT smt(n+5, m);
sort(weight+1, weight+1+m);
for(int i=1; i<=m; i++){
int u, v, c = weight[i].fi;
tie(u, v) = edges[weight[i].se];
if(h[u] < h[v]) swap(u, v);
smt.update(num[u], c, i);
smt.update(clo[u]+1, -c, i);
}
for(int i=1; i<=q; i++){
int u, v, g, s;
cin >> u >> v >> g >> s;
int p = LCA(u, v);
pii fp = smt.get(num[p], m);
pii fu = smt.get(num[u], m);
pii fv = smt.get(num[v], m);
int allG = fu.se + fv.se - fp.se*2;
int res = g+1;
for(int lo=0, hi=m; lo<=hi;){
int mid = (lo+hi)>>1;
pii fp = smt.get(num[p], mid);
pii fu = smt.get(num[u], mid);
pii fv = smt.get(num[v], mid);
int numG = allG - (fu.se + fv.se - fp.se*2);
int numS = fu.fi + fv.fi - fp.fi*2;
if(numG > g) lo = mid + 1;
else if(numS > s) hi = mid - 1;
else res = numG, lo = mid + 1;
}
cout << g - res << endl;
}
}
int32_t main(){
fastIO;
//file(TASK);
nhap();
solve();
return 0;
}
/**
5 4 3
1 2
1 3
2 4
2 5
2 9
2 4
3 5
4 7
3 4 2 11
5 3 4 5
2 3 1 1
10 7 9
1 8
6 3
5 9
7 9
3 1
3 4
10 1
2 6
5 6
9 4
7 4
7 4
2 4
7 4
7 4
1 4
8 6 5 3
3 9 8 0
4 7 6 15
7 4 9 3
6 4 8 0
9 10 5 16
5 3 2 4
2 8 4 3
6 1 3 3
**/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
10680 KB |
Output is correct |
2 |
Correct |
2 ms |
10588 KB |
Output is correct |
3 |
Correct |
2 ms |
10588 KB |
Output is correct |
4 |
Correct |
2 ms |
10588 KB |
Output is correct |
5 |
Correct |
8 ms |
14936 KB |
Output is correct |
6 |
Correct |
10 ms |
15144 KB |
Output is correct |
7 |
Correct |
10 ms |
14496 KB |
Output is correct |
8 |
Correct |
10 ms |
15196 KB |
Output is correct |
9 |
Correct |
10 ms |
15196 KB |
Output is correct |
10 |
Correct |
10 ms |
15116 KB |
Output is correct |
11 |
Correct |
10 ms |
15196 KB |
Output is correct |
12 |
Correct |
10 ms |
15196 KB |
Output is correct |
13 |
Correct |
11 ms |
15196 KB |
Output is correct |
14 |
Correct |
10 ms |
15448 KB |
Output is correct |
15 |
Correct |
10 ms |
15196 KB |
Output is correct |
16 |
Correct |
10 ms |
15192 KB |
Output is correct |
17 |
Correct |
10 ms |
15196 KB |
Output is correct |
18 |
Correct |
10 ms |
15196 KB |
Output is correct |
19 |
Correct |
12 ms |
15352 KB |
Output is correct |
20 |
Correct |
9 ms |
15196 KB |
Output is correct |
21 |
Correct |
9 ms |
15344 KB |
Output is correct |
22 |
Correct |
9 ms |
15196 KB |
Output is correct |
23 |
Correct |
9 ms |
15196 KB |
Output is correct |
24 |
Correct |
11 ms |
15452 KB |
Output is correct |
25 |
Correct |
9 ms |
15196 KB |
Output is correct |
26 |
Correct |
8 ms |
15336 KB |
Output is correct |
27 |
Correct |
9 ms |
15448 KB |
Output is correct |
28 |
Correct |
9 ms |
15196 KB |
Output is correct |
29 |
Correct |
9 ms |
15208 KB |
Output is correct |
30 |
Correct |
9 ms |
15192 KB |
Output is correct |
31 |
Correct |
9 ms |
15196 KB |
Output is correct |
32 |
Correct |
11 ms |
15196 KB |
Output is correct |
33 |
Correct |
10 ms |
15408 KB |
Output is correct |
34 |
Correct |
12 ms |
15192 KB |
Output is correct |
35 |
Correct |
9 ms |
15196 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
10584 KB |
Output is correct |
2 |
Correct |
9 ms |
15196 KB |
Output is correct |
3 |
Correct |
9 ms |
15196 KB |
Output is correct |
4 |
Correct |
11 ms |
15260 KB |
Output is correct |
5 |
Correct |
1113 ms |
181216 KB |
Output is correct |
6 |
Correct |
1497 ms |
158704 KB |
Output is correct |
7 |
Correct |
1335 ms |
137968 KB |
Output is correct |
8 |
Correct |
1030 ms |
134868 KB |
Output is correct |
9 |
Correct |
1012 ms |
141008 KB |
Output is correct |
10 |
Correct |
2005 ms |
198888 KB |
Output is correct |
11 |
Correct |
1961 ms |
198732 KB |
Output is correct |
12 |
Correct |
1941 ms |
198800 KB |
Output is correct |
13 |
Correct |
2047 ms |
198628 KB |
Output is correct |
14 |
Correct |
2353 ms |
198712 KB |
Output is correct |
15 |
Correct |
2304 ms |
204784 KB |
Output is correct |
16 |
Correct |
2176 ms |
200680 KB |
Output is correct |
17 |
Correct |
2217 ms |
204296 KB |
Output is correct |
18 |
Correct |
2235 ms |
198788 KB |
Output is correct |
19 |
Correct |
2333 ms |
198576 KB |
Output is correct |
20 |
Correct |
2383 ms |
199080 KB |
Output is correct |
21 |
Correct |
1016 ms |
198120 KB |
Output is correct |
22 |
Correct |
976 ms |
198340 KB |
Output is correct |
23 |
Correct |
1034 ms |
198332 KB |
Output is correct |
24 |
Correct |
1041 ms |
198620 KB |
Output is correct |
25 |
Correct |
1536 ms |
200468 KB |
Output is correct |
26 |
Correct |
1281 ms |
198260 KB |
Output is correct |
27 |
Correct |
1221 ms |
198420 KB |
Output is correct |
28 |
Correct |
661 ms |
198692 KB |
Output is correct |
29 |
Correct |
647 ms |
198528 KB |
Output is correct |
30 |
Correct |
988 ms |
198780 KB |
Output is correct |
31 |
Correct |
967 ms |
198776 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
10588 KB |
Output is correct |
2 |
Correct |
10 ms |
15416 KB |
Output is correct |
3 |
Correct |
10 ms |
15196 KB |
Output is correct |
4 |
Correct |
10 ms |
15380 KB |
Output is correct |
5 |
Correct |
1166 ms |
145348 KB |
Output is correct |
6 |
Correct |
1150 ms |
122704 KB |
Output is correct |
7 |
Correct |
1780 ms |
173992 KB |
Output is correct |
8 |
Correct |
2545 ms |
205028 KB |
Output is correct |
9 |
Correct |
2376 ms |
204824 KB |
Output is correct |
10 |
Correct |
2293 ms |
205200 KB |
Output is correct |
11 |
Correct |
1715 ms |
205800 KB |
Output is correct |
12 |
Correct |
1715 ms |
205704 KB |
Output is correct |
13 |
Correct |
1694 ms |
203408 KB |
Output is correct |
14 |
Correct |
956 ms |
205228 KB |
Output is correct |
15 |
Correct |
906 ms |
205124 KB |
Output is correct |
16 |
Correct |
1229 ms |
205088 KB |
Output is correct |
17 |
Correct |
1249 ms |
204880 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
10680 KB |
Output is correct |
2 |
Correct |
2 ms |
10588 KB |
Output is correct |
3 |
Correct |
2 ms |
10588 KB |
Output is correct |
4 |
Correct |
2 ms |
10588 KB |
Output is correct |
5 |
Correct |
8 ms |
14936 KB |
Output is correct |
6 |
Correct |
10 ms |
15144 KB |
Output is correct |
7 |
Correct |
10 ms |
14496 KB |
Output is correct |
8 |
Correct |
10 ms |
15196 KB |
Output is correct |
9 |
Correct |
10 ms |
15196 KB |
Output is correct |
10 |
Correct |
10 ms |
15116 KB |
Output is correct |
11 |
Correct |
10 ms |
15196 KB |
Output is correct |
12 |
Correct |
10 ms |
15196 KB |
Output is correct |
13 |
Correct |
11 ms |
15196 KB |
Output is correct |
14 |
Correct |
10 ms |
15448 KB |
Output is correct |
15 |
Correct |
10 ms |
15196 KB |
Output is correct |
16 |
Correct |
10 ms |
15192 KB |
Output is correct |
17 |
Correct |
10 ms |
15196 KB |
Output is correct |
18 |
Correct |
10 ms |
15196 KB |
Output is correct |
19 |
Correct |
12 ms |
15352 KB |
Output is correct |
20 |
Correct |
9 ms |
15196 KB |
Output is correct |
21 |
Correct |
9 ms |
15344 KB |
Output is correct |
22 |
Correct |
9 ms |
15196 KB |
Output is correct |
23 |
Correct |
9 ms |
15196 KB |
Output is correct |
24 |
Correct |
11 ms |
15452 KB |
Output is correct |
25 |
Correct |
9 ms |
15196 KB |
Output is correct |
26 |
Correct |
8 ms |
15336 KB |
Output is correct |
27 |
Correct |
9 ms |
15448 KB |
Output is correct |
28 |
Correct |
9 ms |
15196 KB |
Output is correct |
29 |
Correct |
9 ms |
15208 KB |
Output is correct |
30 |
Correct |
9 ms |
15192 KB |
Output is correct |
31 |
Correct |
9 ms |
15196 KB |
Output is correct |
32 |
Correct |
11 ms |
15196 KB |
Output is correct |
33 |
Correct |
10 ms |
15408 KB |
Output is correct |
34 |
Correct |
12 ms |
15192 KB |
Output is correct |
35 |
Correct |
9 ms |
15196 KB |
Output is correct |
36 |
Correct |
2 ms |
10584 KB |
Output is correct |
37 |
Correct |
9 ms |
15196 KB |
Output is correct |
38 |
Correct |
9 ms |
15196 KB |
Output is correct |
39 |
Correct |
11 ms |
15260 KB |
Output is correct |
40 |
Correct |
1113 ms |
181216 KB |
Output is correct |
41 |
Correct |
1497 ms |
158704 KB |
Output is correct |
42 |
Correct |
1335 ms |
137968 KB |
Output is correct |
43 |
Correct |
1030 ms |
134868 KB |
Output is correct |
44 |
Correct |
1012 ms |
141008 KB |
Output is correct |
45 |
Correct |
2005 ms |
198888 KB |
Output is correct |
46 |
Correct |
1961 ms |
198732 KB |
Output is correct |
47 |
Correct |
1941 ms |
198800 KB |
Output is correct |
48 |
Correct |
2047 ms |
198628 KB |
Output is correct |
49 |
Correct |
2353 ms |
198712 KB |
Output is correct |
50 |
Correct |
2304 ms |
204784 KB |
Output is correct |
51 |
Correct |
2176 ms |
200680 KB |
Output is correct |
52 |
Correct |
2217 ms |
204296 KB |
Output is correct |
53 |
Correct |
2235 ms |
198788 KB |
Output is correct |
54 |
Correct |
2333 ms |
198576 KB |
Output is correct |
55 |
Correct |
2383 ms |
199080 KB |
Output is correct |
56 |
Correct |
1016 ms |
198120 KB |
Output is correct |
57 |
Correct |
976 ms |
198340 KB |
Output is correct |
58 |
Correct |
1034 ms |
198332 KB |
Output is correct |
59 |
Correct |
1041 ms |
198620 KB |
Output is correct |
60 |
Correct |
1536 ms |
200468 KB |
Output is correct |
61 |
Correct |
1281 ms |
198260 KB |
Output is correct |
62 |
Correct |
1221 ms |
198420 KB |
Output is correct |
63 |
Correct |
661 ms |
198692 KB |
Output is correct |
64 |
Correct |
647 ms |
198528 KB |
Output is correct |
65 |
Correct |
988 ms |
198780 KB |
Output is correct |
66 |
Correct |
967 ms |
198776 KB |
Output is correct |
67 |
Correct |
2 ms |
10588 KB |
Output is correct |
68 |
Correct |
10 ms |
15416 KB |
Output is correct |
69 |
Correct |
10 ms |
15196 KB |
Output is correct |
70 |
Correct |
10 ms |
15380 KB |
Output is correct |
71 |
Correct |
1166 ms |
145348 KB |
Output is correct |
72 |
Correct |
1150 ms |
122704 KB |
Output is correct |
73 |
Correct |
1780 ms |
173992 KB |
Output is correct |
74 |
Correct |
2545 ms |
205028 KB |
Output is correct |
75 |
Correct |
2376 ms |
204824 KB |
Output is correct |
76 |
Correct |
2293 ms |
205200 KB |
Output is correct |
77 |
Correct |
1715 ms |
205800 KB |
Output is correct |
78 |
Correct |
1715 ms |
205704 KB |
Output is correct |
79 |
Correct |
1694 ms |
203408 KB |
Output is correct |
80 |
Correct |
956 ms |
205228 KB |
Output is correct |
81 |
Correct |
906 ms |
205124 KB |
Output is correct |
82 |
Correct |
1229 ms |
205088 KB |
Output is correct |
83 |
Correct |
1249 ms |
204880 KB |
Output is correct |
84 |
Correct |
1380 ms |
181704 KB |
Output is correct |
85 |
Correct |
1465 ms |
157452 KB |
Output is correct |
86 |
Correct |
1247 ms |
116744 KB |
Output is correct |
87 |
Correct |
2276 ms |
198596 KB |
Output is correct |
88 |
Correct |
2238 ms |
198664 KB |
Output is correct |
89 |
Correct |
2329 ms |
198476 KB |
Output is correct |
90 |
Correct |
2160 ms |
198480 KB |
Output is correct |
91 |
Correct |
2338 ms |
198888 KB |
Output is correct |
92 |
Correct |
2740 ms |
203080 KB |
Output is correct |
93 |
Correct |
2623 ms |
204068 KB |
Output is correct |
94 |
Correct |
2791 ms |
198712 KB |
Output is correct |
95 |
Correct |
2760 ms |
198700 KB |
Output is correct |
96 |
Correct |
2556 ms |
198652 KB |
Output is correct |
97 |
Correct |
2619 ms |
198532 KB |
Output is correct |
98 |
Correct |
2098 ms |
198448 KB |
Output is correct |
99 |
Correct |
2091 ms |
198284 KB |
Output is correct |
100 |
Correct |
2080 ms |
198496 KB |
Output is correct |
101 |
Correct |
1977 ms |
198388 KB |
Output is correct |
102 |
Correct |
1660 ms |
198464 KB |
Output is correct |
103 |
Correct |
1798 ms |
200556 KB |
Output is correct |
104 |
Correct |
1770 ms |
198192 KB |
Output is correct |
105 |
Correct |
885 ms |
198644 KB |
Output is correct |
106 |
Correct |
786 ms |
198856 KB |
Output is correct |
107 |
Correct |
999 ms |
198500 KB |
Output is correct |
108 |
Correct |
890 ms |
198668 KB |
Output is correct |