Cod sursa(job #2934158)

Utilizator andrei_C1Andrei Chertes andrei_C1 Data 5 noiembrie 2022 14:58:46
Problema A+B Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.45 kb
#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;
}