Pagini recente » Cod sursa (job #1717819) | Cod sursa (job #1811175) | Cod sursa (job #1909375) | Cod sursa (job #1437551) | Cod sursa (job #2934157)
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
ifstream fin("sever.in");
ofstream fout("sever.out");
const int NMAX = 2e5;
const int MMAX = 2e5;
const int QMAX = 2e5;
int N, M, Q;
vector<int> adj[NMAX + 1];
vector<int> gang[MMAX + 1]; // bang
int toler[MMAX + 1];
int answer[MMAX + 1];
struct Update {
int u, v;
};
struct Range {
int left, right, mid, ans;
int idx;
bool operator < (const Range &oth) const {
return mid < oth.mid;
}
};
Update updates[QMAX + 1];
Range gangAns[MMAX + 1];
int lvl[NMAX + 1];
int sz[NMAX + 1], parent[NMAX + 1];
void dfs(int u = 1, int v = 0) {
parent[u] = v;
sz[u] = 1;
lvl[u] = lvl[v] + 1;
for(const auto &it: adj[u]) if(it != v) {
dfs(it, u);
sz[u] += sz[it];
}
}
int tin[NMAX + 1], label[NMAX + 1];
vector<int> heavyTour;
vector<int> head = {1};
void decomp(int u = 1, int v = 0) {
label[u] = head.size() - 1;
heavyTour.push_back(u);
tin[u] = heavyTour.size();
int heavyChild = 0;
for(const auto &it: adj[u]) if(it != v) {
if(sz[it] > sz[heavyChild]) {
heavyChild = it;
}
}
if(heavyChild != 0) {
decomp(heavyChild, u);
for(const auto &it: adj[u]) if(it != v && it != heavyChild) {
head.push_back(it);
decomp(it, u);
}
}
}
int aib[NMAX + 2];
int lsb(int x) {
return x & (-x);
}
void reset() {
for(int i = 0; i <= N + 1; i++) {
aib[i] = 0;
}
}
int query(int pos) {
int ret = 0;
for(int i = pos; i > 0; i -= lsb(i)) {
ret += aib[i];
}
return ret;
}
int queryNode(int u) {
return query(tin[u]);
}
void update(int pos, int val) {
assert(pos > 0);
for(int i = pos; i <= N; i += lsb(i)) {
aib[i] += val;
}
}
void updateRange(int left, int right) {
update(left, 1);
update(right + 1, -1);
}
void updateChain(int u, int v) {
while(label[u] != label[v] && u != 0 && v != 0) {
// cout << u << " " << v << '\n';
if(lvl[head[label[u]]] > lvl[head[label[v]]]) {
// cout << head[label[u]] << " " << u << '\n';
updateRange(tin[head[label[u]]], tin[u]);
u = parent[head[label[u]]];
} else {
// cout << head[label[v]] << " " << v << '\n';
updateRange(tin[head[label[v]]], tin[v]);
v = parent[head[label[v]]];
}
}
if(tin[u] > tin[v]) {
swap(u, v);
}
// cout << u << " " << v << '\n';
updateRange(tin[u], tin[v]);
}
int main() {
ios_base :: sync_with_stdio(false);
fin >> N >> M;
for(int i = 1; i < N; i++) {
int u, v;
fin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs();
// for(int i = 1; i <= N; i++) {
// cout << sz[i] << " " << lvl[i] << '\n';
// }
decomp();
label[1] = 0;
// for(const auto &it: heavyTour) {
// cout << it << " " << label[it] << " " << head[label[it]] << '\n';
// }
// cout << '\n';
// updateChain(8, 4);
// updateChain(1, 7);
// cout << queryNode(8) << '\n';
for(int i = 1; i <= N; i++) {
int gangType;
fin >> gangType;
gang[gangType].push_back(i);
}
// for(int i = 1; i <= M; i++) {
// for(const auto &it: gang[i]) {
// cout << it << " ";
// }
// cout << '\n';
// }
for(int i = 1; i <= M; i++) {
fin >> toler[i];
}
fin >> Q;
for(int i = 1; i <= Q; i++) {
fin >> updates[i].u >> updates[i].v;
// updateChain(updates[i].u, updates[i].v);
}
// for(int i = 1; i <= N; i++) {
// cout << queryNode(i) << '\n';
// }
for(int i = 1; i <= M; i++) {
gangAns[i].left = 0;
gangAns[i].right = Q;
gangAns[i].mid = (gangAns[i].left + gangAns[i].right) >> 1;
gangAns[i].idx = i;
gangAns[i].ans = -1;
}
for(int pw = 1; pw <= Q; pw <<= 1) {
reset();
sort(gangAns + 1, gangAns + M + 1);
// for(int i = 1; i <= M; i++) {
// cout << gangAns[i].idx << " " << gangAns[i].mid << "; ";
// }
// cout << '\n';
int idx = 1;
for(int i = 1; i <= Q && idx <= M; i++) {
updateChain(updates[i].u, updates[i].v);
while(idx <= M && gangAns[idx].mid == i) {
int sum = 0;
for(const auto &it: gang[gangAns[idx].idx]) {
sum += queryNode(it);
}
// cout << gangAns[idx].idx << " " << sum << " " << toler[gangAns[idx].idx] << '\n';
if(sum <= toler[gangAns[idx].idx]) {
gangAns[idx].left = gangAns[idx].mid + 1;
gangAns[idx].mid = (gangAns[idx].left + gangAns[idx].right) >> 1;
} else {
gangAns[idx].right = gangAns[idx].mid - 1;
gangAns[idx].ans = gangAns[idx].mid;
gangAns[idx].mid = (gangAns[idx].left + gangAns[idx].right) >> 1;
}
idx++;
}
}
}
for(int i = 1; i <= M; i++) {
answer[gangAns[i].idx] = gangAns[i].ans;
}
for(int i = 1; i <= M; i++) {
fout << answer[i] << " ";
}
return 0;
}