#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 1e5 + 10;
struct checkpoint
{
int p, c;
void read()
{
cin >> p >> c;
}
bool operator < (const checkpoint &t) const
{
return c < t.c;
}
} cp[maxn];
struct citizen
{
int s, t, x, y;
void read()
{
cin >> s >> t >> x >> y;
}
} ct[maxn];
int n, m, q;
vector < int > adj[maxn];
pair < int, int > road[maxn];
void input()
{
cin >> n >> m >> q;
for (int i = 1; i < n; i ++)
{
int a, b;
cin >> a >> b;
road[i] = {a, b};
adj[a].push_back(b);
adj[b].push_back(a);
}
for (int i = 1; i <= m; i ++)
cp[i].read();
for (int i = 1; i <= q; i ++)
ct[i].read();
}
int tin[maxn], tout[maxn], timer, occ[2 * maxn];
int par[maxn], depth[maxn];
void euler_tour(int v = 1, int p = 0)
{
occ[++ timer] = v;
tin[v] = timer;
for (int u : adj[v])
{
if (u == p)
continue;
depth[u] = depth[v] + 1;
par[u] = v;
euler_tour(u, v);
occ[++ timer] = v;
}
tout[v] = timer;
}
const int maxlog = 20;
struct sparse_table
{
int lg[2 * maxn], dp[maxlog][2 * maxn];
void build_sparse_table()
{
for (int i = 1; i <= timer; i ++)
{
lg[i] = lg[i / 2] + 1;
dp[0][i] = occ[i];
}
for (int j = 1; j < lg[timer]; j ++)
{
for (int i = 1; i <= timer - (1 << j) + 1; i ++)
{
dp[j][i] = dp[j - 1][i + (1 << (j - 1))];
if (depth[dp[j - 1][i]] < depth[dp[j][i]])
dp[j][i] = dp[j - 1][i];
}
}
/**cout << "---------------" << endl;
for (int j = 0; j < lg[timer]; j ++, cout << endl)
for (int i = 1; i <= timer; i ++)
cout << dp[j][i] << " ";*/
}
int lca_query(int v, int u)
{
int l = tin[v], r = tin[u];
if (l > r)
swap(l, r);
int len = lg[r - l + 1] - 1, lca = dp[len][r - (1 << len) + 1];
///cout << "lca " << v << " " << u << " " << l << " " << r << endl;
if (depth[dp[len][l]] < depth[lca])
lca = dp[len][l];
return lca;
}
};
sparse_table st;
struct fenwick
{
ll fen[2 * maxn];
void add(int pos, ll val)
{
for (int i = pos; i <= timer; i += (i & -i))
fen[i] += val;
}
ll sum(int pos)
{
ll s = 0;
for (int i = pos; i > 0; i -= (i & -i))
s += fen[i];
return s;
}
void range_update(int left, int right, ll val)
{
add(left, val);
add(right + 1, - val);
}
ll query(int pos)
{
return sum(pos);
}
};
fenwick gold, silver;
pair < int, int > range[maxn];
vector < int > upd[maxn];
int binary_position(int val)
{
int left = 1, right = m;
while(left <= right)
{
int mid = left + (right - left) / 2;
if (cp[mid].c <= val)
left = mid + 1;
else
right = mid - 1;
}
return right;
}
int ans[maxn];
void parallel_binary_search()
{
for (int i = 1; i <= q; i ++)
{
range[i] = {0, 1e9 + 10};
}
for (int i = 1; i < n; i ++)
{
if (depth[road[i].first] < depth[road[i].second])
swap(road[i].first, road[i].second);
}
/**for (int i = 1; i <= m; i ++)
{
cout << road[cp[i].p].first << endl;
}*/
sort(cp + 1, cp + m + 1);
while(true)
{
bool done = true;
for (int i = 0; i <= m; i ++)
upd[i].clear();
for (int i = 1; i <= q; i ++)
{
if (range[i].first <= range[i].second)
{
done = false;
int mid = (range[i].first + (range[i].second - range[i].first) / 2);
int pos = binary_position(mid);
upd[pos].push_back(i);
}
}
if (done)
break;
//for (int i = 1; i <= m; i ++)
// gold.range_update(tin[cp[i].p], tout[cp[i].p], 1);
/**cout << "-------------" << endl;
for (int i = 1; i <= m; i ++)
cout << range[i].first << " " << range[i].second << endl;*/
for (int i = 0; i <= m; i ++)
{
if (i != 0)
{
silver.range_update(tin[road[cp[i].p].first], tout[road[cp[i].p].first], cp[i].c);
}
for (int idx : upd[i])
{
int lca = st.lca_query(ct[idx].s, ct[idx].t);
ll val = silver.query(tin[ct[idx].s]) + silver.query(tin[ct[idx].t]);
val = val - 2 * silver.query(tin[lca]);
///co
///cout << idx << " : " << val << " -- " << lca << endl;
int mid = (range[idx].first + (range[idx].second - range[idx].first) / 2);
if (val > ct[idx].y)
range[idx].second = mid - 1;
else
range[idx].first = mid + 1;
}
}
for (int i = 1; i <= m; i ++)
silver.range_update(tin[road[cp[i].p].first], tout[road[cp[i].p].first], -cp[i].c);
}
for (int i = 0; i <= m; i ++)
upd[i].clear();
for (int i = 1; i <= q; i ++)
{
int pos = binary_position(range[i].second);
upd[pos].push_back(i);
}
for (int i = 1; i <= m; i ++)
{
gold.range_update(tin[road[cp[i].p].first], tout[road[cp[i].p].first], 1);
}
for (int i = 0; i <= m; i ++)
{
if (i != 0)
{
silver.range_update(tin[road[cp[i].p].first], tout[road[cp[i].p].first], cp[i].c);
gold.range_update(tin[road[cp[i].p].first], tout[road[cp[i].p].first], -1);
}
/**cout << "step" << endl;
cout << i << endl;
for (int j = 1; j <= n; j ++)
cout << gold.query(tin[j]) << " ";
cout << endl;
cout << "order" << endl;
for (int j = 1; j <= timer; j ++)
cout << occ[j] << " ";
cout << endl;*/
for (int idx : upd[i])
{
int lca = st.lca_query(ct[idx].s, ct[idx].t);
ll val = silver.query(tin[ct[idx].s]) + silver.query(tin[ct[idx].t]);
val = val - 2 * silver.query(tin[lca]);
ll min_gold = gold.query(tin[ct[idx].s]) + gold.query(tin[ct[idx].t]);
///cout << "gold " << min_gold << " " << gold.query(tinendl;
min_gold = min_gold - 2 * gold.query(tin[lca]);
//cout << idx << " : " << min_gold << " " << i << " lca " << lca << endl;
int left_gold = ct[idx].x - min_gold;
if (left_gold < 0)
left_gold = - 1;
ans[idx] = left_gold;
}
}
for (int i = 1; i <= q; i ++)
cout << ans[i] << endl;
}
void solve()
{
input();
euler_tour(1, 0);
st.build_sparse_table();
parallel_binary_search();
}
int main()
{
speed();
solve();
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
5076 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
5076 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
5844 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
5076 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
5076 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
