#include<iostream>
#include<stdio.h>
#include<stdint.h>
#include<iomanip>
#include<algorithm>
#include<utility>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<deque>
#include<math.h>
#include<assert.h>
#include<string.h>
#include<chrono>
#include<bitset>
using namespace std;
using namespace std::chrono;
const int64_t INF = (int64_t) 1e18 + 100;
const int64_t mINF = (int64_t) 2 * 1e9 + 5;
const int64_t MOD = (int64_t) 20230401;
const int64_t MOD2 = 998244353;
const int nbit = 63;
const int ndig = 10;
const int nchar = 26;
const int p1 = 31;
const int p2 = 53;
const int D = 4;
int dr[D] = {-1, 0, 1, 0};
int dc[D] = {0, 1, 0, -1};
const int Dk = 8;
int drk[Dk] = {2, 2, -2, -2, 1, 1, -1, -1};
int dck[Dk] = {1, -1, 1, -1, 2, -2, 2, -2};
struct Query
{
int s;
int t;
int x;
int y;
Query(int s_, int t_, int x_, int y_) : s(s_), t(t_), x(x_), y(y_) {}
};
struct Path
{
int u;
int w;
Path(int u_, int w_) : u(u_), w(w_) {}
bool operator < (const Path& o) const
{
return w < o.w;
}
};
struct Solution
{
int n;
int m;
int q;
int t;
int k;
int LOG;
vector<int> f;
vector<int> pos;
vector<int> tin;
vector<int> tout;
vector<int> depth;
vector<Path> path;
vector<vector<int> > rmq;
vector<vector<int> > adj;
Solution() {}
void solve()
{
cin >> n >> m >> q;
t = 1; k = 0;
f.resize(n);
tin.resize(n, 0);
tout.resize(n, 0);
depth.resize(n, 0);
adj.resize(n);
vector<pair<int, int> > edges;
for(int i = 0; i < n - 1; i++)
{
int u; int v;
cin >> u >> v;
u--; v--;
edges.emplace_back(u, v);
adj[u].push_back(v);
adj[v].push_back(u);
}
DFS();
LOG = 0;
while(MASK(LOG) <= k) LOG++;
rmq.resize(LOG, vector<int>(k, 0));
for(int i = 0; i < k; i++)
{
rmq[0][i] = pos[i];
}
for(int i = 1; i < LOG; i++)
{
for(int j = 0; j + MASK(i) - 1 < k; j++)
{
int d1 = depth[ rmq[i - 1][j] ];
int d2 = depth[ rmq[i - 1][j + MASK(i - 1)] ];
if(d1 < d2) rmq[i][j] = rmq[i - 1][j];
else rmq[i][j] = rmq[i - 1][j + MASK(i - 1)];
}
}
for(int i = 0; i < m; i++)
{
int id; int c;
cin >> id >> c;
id--;
int u = edges[id].first;
int v = edges[id].second;
if(depth[u] > depth[v]) swap(u, v);
path.emplace_back(v, c);
}
sort(path.begin(), path.end());
vector<Query> qury;
for(int i = 0; i < q; i++)
{
int s; int e; int x; int y;
cin >> s >> e >> x >> y;
s--; e--;
qury.emplace_back(s, e, x, y);
}
vector<int64_t> gold(t + 1, 0);
vector<int64_t> silver(t + 1, 0);
vector<int> l(q, 0);
vector<int> r(q, m);
vector<int> ans(q, -1);
while(true)
{
fill(gold.begin(), gold.end(), 0);
fill(silver.begin(), silver.end(), 0);
for(int i = 0; i < m; i++)
{
int u = path[i].u;
update(tin[u], 1, gold);
update(tout[u], -1, gold);
}
vector<pair<int, int> > mid;
for(int i = 0; i < q; i++)
{
if(l[i] > r[i]) continue;
int md = l[i] + (r[i] - l[i]) / 2;
mid.emplace_back(md, i);
}
if((int) mid.size() == 0) break;
sort(mid.begin(), mid.end());
int id = 0;
for(int i = 0; i < m; i++)
{
while(id < (int) mid.size() && mid[id].first == i)
{
int j = mid[id].second;
int s = qury[j].s; int e = qury[j].t; int x = qury[j].x; int y = qury[j].y;
int lca = LCA(s, e);
int sums = sum(tin[s], silver) + sum(tin[e], silver) - 2 * sum(tin[lca], silver);
int sumg = sum(tin[s], gold) + sum(tin[e], gold) - 2 * sum(tin[lca], gold);
if(x >= sumg && y >= sums)
{
ans[j] = x - sumg;
l[j] = mid[id].first + 1;
}
else if(x < sumg) l[j] = mid[id].first + 1;
else if(y < sums) r[j] = mid[id].first - 1;
id++;
}
int u = path[i].u;
int w = path[i].w;
update(tin[u], -1, gold); update(tout[u], 1, gold);
update(tin[u], w, silver); update(tout[u], -w, silver);
}
while(id < (int) mid.size())
{
int j = mid[id].second;
int s = qury[j].s; int e = qury[j].t; int x = qury[j].x; int y = qury[j].y;
int lca = LCA(s, e);
int sums = sum(tin[s], silver) + sum(tin[e], silver) - 2 * sum(tin[lca], silver);
int sumg = sum(tin[s], gold) + sum(tin[e], gold) - 2 * sum(tin[lca], gold);
if(x >= sumg && y >= sums)
{
ans[j] = x - sumg;
l[j] = mid[id].first + 1;
}
else if(x < sumg) l[j] = mid[id].first + 1;
else if(y < sums) r[j] = mid[id].first - 1;
id++;
}
}
for(int i = 0; i < q; i++)
{
cout << ans[i] << "\n";
}
}
int LCA(int i, int j)
{
i = f[i]; j = f[j];
if(i > j) swap(i, j);
int len = j - i + 1;
int kk = 31 - __builtin_clz(len);
if(depth[ rmq[kk][i] ] < depth[ rmq[kk][j - MASK(kk) + 1] ]) return rmq[kk][i];
return rmq[kk][j - MASK(kk) + 1];
}
void DFS(int u = 0, int p = -1)
{
f[u] = k++;
tin[u] = t++;
pos.push_back(u);
for(int i = 0; i < (int) adj[u].size(); i++)
{
int v = adj[u][i];
if(v == p) continue;
depth[v] = depth[u] + 1;
DFS(v, u);
pos.push_back(u);
k++;
}
tout[u] = t++;
}
void update(int i, int val, vector<int64_t>& bit)
{
while(i < (int) bit.size())
{
bit[i] += val;
i += i & (-i);
}
}
int64_t sum(int i, vector<int64_t>& bit)
{
int64_t ans = 0;
while(i > 0)
{
ans += bit[i];
i -= i & (-i);
}
return ans;
}
int modadd(int t1, int t2)
{
int res = t1 + t2;
if(res >= MOD) res -= MOD;
return res;
}
int modsub(int t1, int t2)
{
int res = t1 - t2;
if(res < 0) res += MOD;
return res;
}
int modmul(int t1, int t2)
{
int64_t res = 1LL * t1 * t2;
return res % MOD;
}
int64_t Abs(int64_t t1)
{
if(t1 < 0) return -t1;
return t1;
}
int64_t MASK(int j)
{
return (1LL << j);
}
bool BIT(int64_t t1, int j)
{
return (t1 & MASK(j));
}
};
void __setup()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
}
int main()
{
__setup();
// auto start = high_resolution_clock::now();
int t = 1;
// cin >> t;
for(int i = 1; i <= t; i++)
{
Solution().solve();
}
// auto stop = high_resolution_clock::now();
// auto duration = duration_cast<microseconds>(stop - start);
// cerr << duration.count() << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Runtime error |
3 ms |
1628 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Runtime error |
3 ms |
1628 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
1884 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Runtime error |
3 ms |
1628 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
