Участник:ZhenyaStrelkova/ADAPHONE

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/ADAPHONE/

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
 
using namespace std;
 
const int max_n = 200007;
const int max_k = 18;
struct Node {
    int l, r, z, id;
};
 
std::vector<int> edges[max_n];
int dep[max_n], f[max_n][max_k + 1];
int st[max_n], ed[max_n], loc[max_n << 1];
int P, dfn;
int vis[max_n], ret_val;
Node query_[max_n];
 
bool comparator(const Node &lhs, const Node &rhs) {
    return lhs.l / P == rhs.l / P ? lhs.r < rhs.r : lhs.l / P < rhs.l / P;
}
 
void dfs(int x, int par) {
    st[x] = dfn++;
    loc[st[x]] = x;
    for (int i = 1; i <= max_k; ++i) {
        f[x][i] = f[f[x][i - 1]][i - 1];
    }
    for (auto &y: edges[x]) {
        if (y != par) {
            dep[y] = dep[f[y][0] = x] + 1;
            dfs(y, x);
        }
    }
    loc[ed[x] = dfn++] = x;
}
 
int lca(int x, int y) {
    if (x == y)
        return x;
    if (dep[x] < dep[y]) {
        swap(x, y);
    }
    for (int i = max_k; i >= 0; --i) {
        if (dep[f[x][i]] >= dep[y])
            x = f[x][i];
    }
    if (x == y)
        return x;
    for (int i = max_k; i >= 0; --i) {
        if (f[x][i] == f[y][i])
            continue;
        x = f[x][i];
        y = f[y][i];
 
    }
    return f[x][0];
}
 
void deal(int x) {
    if (vis[x]) {
        if (vis[x - 1] && vis[x + 1])
            ++ret_val;
        else if (!vis[x - 1] && !vis[x + 1])
            --ret_val;
    } else {
        if (vis[x - 1] && vis[x + 1])
            --ret_val;
        else if (!vis[x - 1] && !vis[x + 1])
            ++ret_val;
    }
    vis[x] ^= 1;
}
 
int main() {
    int N, Q;
    cin >> N >> Q;
    for (int i = 1; i < N; ++i) {
        int u, v;
        cin >> u >> v;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    dfs(dep[1] = 1, -1);
    P = sqrt(N * 2);
    vector<int> ret(Q);
    for (int i = 0; i < Q; ++i) {
        int x, y;
        cin >> x >> y;
        if (st[x] > st[y])
            swap(x, y);
        int z = lca(x, y);
        query_[i].id = i;
        if (z == x) {
            query_[i].l = st[x];
            query_[i].r = st[y];
        }
        else {
            query_[i].l = ed[x];
            query_[i].r = st[y];
            query_[i].z = z;
        }
    }
    sort(query_, query_ + Q, comparator);
    for (int i = 0, l = 0, r = -1; i < Q; ++i) {
        while (r < query_[i].r) deal(loc[++r]);
        while (r > query_[i].r) deal(loc[r--]);
        while (l < query_[i].l) deal(loc[l++]);
        while (l > query_[i].l) deal(loc[--l]);
        if (query_[i].z)
            deal(query_[i].z);
        ret[query_[i].id] = ret_val;
        if (query_[i].z)
            deal(query_[i].z);
    }
 
    for (int i = 0; i < Q; ++ i) {
        cout << ret[i] <<"\n";
    }
    return 0;
}