Cod sursa(job #3359717)

Utilizator TimofeiFilipTimofei Filip Emanuel TimofeiFilip Data 2 iulie 2026 21:37:14
Problema Stramosi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.26 kb
#include<cstdio>
#include<vector>
#include<stack>
using namespace std;
const int NMAX = 1e5 + 10;
const int LOG_MAX = 20;


vector<int> adj[NMAX];
vector<int> heights(NMAX + 1, 0);
int ancestors[NMAX][LOG_MAX];
bool visited[NMAX];
int nodes;


void compute_heights(int current_node, int current_height) {
    heights[current_node] = current_height;
    visited[current_node] = true;
    for (auto node : adj[current_node]) {
        if (!visited[node]) {
            ancestors[node][0] = current_node;
            compute_heights(node, current_height + 1);
        }
    }
}

void compute_ancestors() {

    for (int j = 1; j < LOG_MAX; j++) {
        for (int i = 1; i <= nodes; i++) {
            ancestors[i][j] = ancestors[ancestors[i][j - 1]][j - 1];
        }
    }
}
int MSB(const int &x) {
    return 31 - __builtin_clz(x);
}
int get_pth_ancestor(const int q, int p) {
    int ancestor = q;
    while (p != 0) {
        if (ancestor == 0) {
            break;
        }
        int jump_positions = MSB(p);
        ancestor = ancestors[ancestor][jump_positions];
        p -= (1 << jump_positions);
    }
    return ancestor;
}

bool is_ancestor(int x, int y) {
    if (heights[x] == heights[y] && x != y) return false;
    if (heights[x] == heights[y] && x == y) return true;
    int start_node, end_node;
    if (heights[x] > heights[y]){
        start_node = x;
        end_node = y;
    }
    else {
        start_node = y;
        end_node = x;
    }
    int height_difference = heights[start_node] - heights[end_node];
    int ancestor = get_pth_ancestor(start_node, height_difference);
    return (ancestor == end_node);
}
int main() {
    freopen("maimute.in", "r", stdin);
    freopen("maimute.out", "w", stdout);
    int n;
    scanf("%d", &n);
    for (; n > 1; n--) {
        int x, y;
        scanf("%d %d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
        nodes = max(nodes, max(x, y));
    }

    compute_heights(1, 0);
    compute_ancestors();

    int queries;
    scanf("%d", &queries);
    for (; queries > 0; queries--) {
        int x, y;
        scanf("%d %d", &x, &y);
        //printf("%d %d\n", x, y);
        bool ancestor = is_ancestor(x, y);
        if (ancestor)
            printf("DA\n");
        else
            printf("NU\n");
    }
    return 0;
}