This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define F first
#define S second
#define pb push_back
#define all(x) x.begin() , x.end()
#define debug while(1) cout << "Test\n"
const int N = 1e5 + 10;
const int mod = 1e9 + 7;
const int INF = 1e18 + 10;
int n , m , q;
int seg[N << 2];
int f[N];
int l[N];
int r[N];
int mid[N];
vector<int> g[N];
vector<pair<int , int>> e;
vector<pair<int , int>> vec;
int x[N];
int y[N];
int s[N];
int en[N];
int par[N][20];
int lc[N];
vector<int> qu[N];
int st[N];
int fn[N];
int h[N];
int tim;
void dfs(int v) {
st[v] = ++tim;
for(int i = 1 ; i < 20 ; i++)
par[v][i] = par[par[v][i-1]][i-1];
for(auto u : g[v]) if(u != par[v][0]) {
par[u][0] = v;
h[u] = h[v] + 1;
dfs(u);
}
fn[v] = tim;
}
int lca(int v , int u) {
if(h[v] < h[u]) swap(v , u);
int he = h[v] - h[u];
for(int i = 0 ; i < 20 ; i++) if((1ll << i) & he)
v = par[v][i];
if(v == u) return v;
for(int i = 19 ; ~i ; i--)
if(par[v][i] != par[u][i]) v = par[v][i] , u = par[u][i];
return par[v][0];
}
void upd(int v , int tl , int tr , int l , int r , int x) {
// cout << v << " " << tl << " " << tr << " " << l << " " << r << " " << x << "\n";
if(l > r) return;
if(tl == l && tr == r) {
seg[v] += x;
return;
}
int tm = (tl + tr) >> 1;
int cl = v << 1 , cr = cl | 1;
upd(cl , tl , tm , l , min(tm , r) , x);
upd(cr , tm + 1 , tr , max(tm+1 , l) , r , x);
}
int ask(int v , int tl , int tr , int p) {
if(tl == tr) return seg[v];
int tm = (tl + tr) >> 1;
int cl = v << 1 , cr = cl | 1;
if(tm >= p) return ask(cl , tl , tm , p) + seg[v];
return ask(cr , tm+1 , tr , p) + seg[v];
}
void solve() {
cin >> n >> m >> q;
for(int i = 1 ; i < n ; i++) {
int v , u;
cin >> v >> u;
e.pb({v , u});
g[v].pb(u);
g[u].pb(v);
}
dfs(1);
for(int i = 1 ; i <= m ; i++) {
int id , x;
cin >> id >> x;
vec.pb({x , id});
}
sort(all(vec));
for(int i = 1 ; i <= q ; i++) {
cin >> s[i] >> en[i] >> x[i] >> y[i];
lc[i] = lca(s[i] , en[i]);
l[i] = 0;
r[i] = m+1;
mid[i] = (l[i] + r[i]) >> 1;
qu[mid[i]].pb(i);
}
for(int i = 1 ; i <= m ; i++) {
// cout << "kir " << i << "\n";
int v = e[vec[i-1].S-1].F;
int u = e[vec[i-1].S-1].S;
if(v == par[u][0]) swap(v , u);
upd(1 , 1 , n , st[v] , fn[v] , 1);
}
for(int i = 1 ; i <= q ; i++)
f[i] = ask(1 , 1 , n , st[s[i]]) + ask(1 , 1 , n , st[en[i]]) - 2 * ask(1 , 1 , n , st[lc[i]]); // , cout << i << " " << f[i] << "\n";
for(int t = 1 ; t <= 20 ; t++) {
for(int i = 1 ; i <= 4 * n ; i++)
seg[i] = 0;
for(int i = 1 ; i <= m ; i++) {
int v = e[vec[i-1].S-1].F;
int u = e[vec[i-1].S-1].S;
if(v == par[u][0]) swap(v , u);
upd(1 , 1 , n , st[v] , fn[v] , vec[i-1].F);
for(auto id : qu[i]) {
// if(id == 1) cout << l[id] << " " << r[id] << " " << mid[id] << " oo " << ask(1 , 1 , n , st[s[id]]) + ask(1 , 1 , n , st[en[id]]) - 2 * ask(1 , 1 , n , st[lc[id]]) << "\n";
if(ask(1 , 1 , n , st[s[id]]) + ask(1 , 1 , n , st[en[id]]) - 2 * ask(1 , 1 , n , st[lc[id]]) <= y[id])
l[id] = mid[id];
else
r[id] = mid[id];
mid[id] = (l[id] + r[id]) >> 1;
}
}
for(int i = 1 ; i <= m ; i++)
qu[i].clear();
for(int i = 1 ; i <= q ; i++)
qu[mid[i]].pb(i);
}
// for(int i = 1 ; i <= q ; i++)
// cout << l[i] << " " << r[i] << " " << mid[i] << "\n";
// cout << "khob kir\n";
for(int i = 1 ; i <= 4 * n ; i++)
seg[i] = 0;
for(int i = 1 ; i <= m ; i++) {
int v = e[vec[i-1].S-1].F;
int u = e[vec[i-1].S-1].S;
if(v == par[u][0]) swap(v , u);
upd(1 , 1 , n , st[v] , fn[v] , 1);
for(auto id : qu[i]) f[id] -= ask(1 , 1 , n , st[s[id]]) + ask(1 , 1 , n , st[en[id]]) -
2 * ask(1 , 1 , n , st[lc[id]]);
}
for(int i = 1 ; i <= q ; i++)
cout << max(-1ll , x[i] - f[i]) << "\n";
// cout << "GA\n";
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n = 1;
// cin >> n;
while(n--)
solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |