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;
namespace
{
template <typename Fun>
struct YCombinator
{
template <typename T>
YCombinator(T &&_fun) : fun(forward<T>(_fun)) {}
template <typename... Args>
decltype(auto) operator()(Args &&...args) { return fun(ref(*this), forward<Args>(args)...); }
private:
Fun fun;
};
template <typename T>
YCombinator(T &&) -> YCombinator<decay_t<T>>;
} // namespace
struct DSU
{
DSU(int n) : e(n, -1) {}
int find(int u) { return e[u] < 0 ? u : e[u] = find(e[u]); }
bool same(int u, int v) { return find(u) == find(v); }
bool unite(int u, int v)
{
u = find(u);
v = find(v);
if (u == v)
return 0;
if (e[u] > e[v])
swap(u, v);
e[u] += e[v];
e[v] = u;
return 1;
}
vector<int> e;
};
template <typename T>
struct Fenwick
{
Fenwick(int _n) : n(_n), tree(n + 1) {}
T sum(int p)
{
T ret = 0;
for (; p; p -= p & -p)
ret += tree[p];
return ret;
}
void add(int p, T x)
{
for (p++; p <= n; p += p & -p)
tree[p] += x;
}
int n;
vector<T> tree;
};
void solve()
{
int n, m, q;
cin >> n >> m >> q;
vector<vector<pair<int, int>>> adj(n);
for (int i = 0; i < n - 1; i++)
{
int u, v;
cin >> u >> v, --u, --v;
adj[u].emplace_back(v, i);
adj[v].emplace_back(u, i);
}
vector<pair<long, int>> a(m);
for (auto &[x, j] : a)
cin >> j >> x, --j;
sort(a.begin(), a.end());
vector<int> s(q), t(q);
vector<long> gold(q), silver(q);
for (int i = 0; i < q; i++)
cin >> s[i] >> t[i] >> gold[i] >> silver[i], --s[i], --t[i];
vector<int> to(n - 1), tin(n), tout(n), pref(n);
int timer = 0;
YCombinator(
[&](auto self, int u, int p) -> void
{
tin[u] = timer++;
for (auto [v, j] : adj[u])
{
if (v != p)
{
to[j] = v;
self(v, u);
}
}
tout[u] = timer;
})(0, -1);
for (auto [x, j] : a)
pref[to[j]]++;
YCombinator(
[&](auto self, int u, int p) -> void
{
if (p != -1)
pref[u] += pref[p];
for (auto [v, j] : adj[u])
{
if (v != p)
self(v, u);
}
})(0, -1);
for (int i = 0; i < q; i++)
{
if (tin[s[i]] > tin[t[i]])
swap(s[i], t[i]);
}
vector<int> lca(q), cnt(q);
{
vector<int> anc(n);
DSU dsu(n);
vector<vector<int>> todo(n);
for (int i = 0; i < q; i++)
todo[t[i]].push_back(i);
YCombinator(
[&](auto self, int u, int p) -> void
{
for (auto [v, j] : adj[u])
{
if (v != p)
{
self(v, u);
dsu.unite(u, v);
anc[dsu.find(u)] = u;
}
}
for (int j : todo[u])
lca[j] = anc[dsu.find(s[j])];
})(0, -1);
}
for (int i = 0; i < q; i++)
cnt[i] = pref[s[i]] + pref[t[i]] - 2 * pref[lca[i]];
vector res = cnt;
vector<int> lo(q, 0), hi(q, m);
while (1)
{
vector<vector<int>> met(m);
bool flag = 0;
for (int i = 0; i < q; i++)
{
if (lo[i] < hi[i])
{
met[(lo[i] + hi[i] - 1) / 2].push_back(i);
flag = 1;
}
}
if (!flag)
break;
Fenwick<long> fenw_cost(n);
Fenwick<int> fenw_cnt(n);
auto path_cost = [&](int k) -> long
{ return fenw_cost.sum(tin[s[k]] + 1) + fenw_cost.sum(tin[t[k]] + 1) - 2 * fenw_cost.sum(tin[lca[k]] + 1); };
auto path_cnt = [&](int k) -> int
{ return fenw_cnt.sum(tin[s[k]] + 1) + fenw_cnt.sum(tin[t[k]] + 1) - 2 * fenw_cnt.sum(tin[lca[k]] + 1); };
for (int i = 0; i < m; i++)
{
auto [x, j] = a[i];
fenw_cost.add(tin[to[j]], x);
fenw_cost.add(tout[to[j]], -x);
fenw_cnt.add(tin[to[j]], 1);
fenw_cnt.add(tout[to[j]], -1);
for (int k : met[i])
{
if (path_cost(k) > silver[k])
hi[k] = i;
else
{
res[k] = cnt[k] - path_cnt(k);
lo[k] = i + 1;
}
}
}
}
for (int i = 0; i < q; i++)
cout << max(gold[i] - res[i], -1l) << '\n';
}
int main()
{
ios_base::sync_with_stdio(false), cin.tie(NULL);
solve();
return 0;
}
# | 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... |