Submission #905774

---

Source Code Expand

#include <cstdio>
#include <vector>
using namespace std;

const int N = 200500;

vector<int> E[N];
vector<int> F[N];

const int LGN = 18;
int up[LGN][N];
int D[N];

void DFS(int x, int p = -1) {
    D[x] = (p == -1) ? 0 : D[p] + 1;
    up[0][x] = (p == -1) ? x : p;
    for (int d = 1; d < LGN; d++)
        up[d][x] = up[d - 1][up[d - 1][x]];
    for (int y : E[x]) {
        if (y != p)
            DFS(y, x);
    }
}

inline int lca(int a, int b) {
    if (D[a] > D[b]) {
        swap(a, b);
    }
    for (int d = LGN - 1; d >= 0; d--)
        if (D[up[d][b]] >= D[a])
            b = up[d][b];
    if (a == b)
        return a;
    for (int d = LGN - 1; d >= 0; d--)
        if (up[d][a] != up[d][b])
            a = up[d][a], b = up[d][b];
    return up[0][a];
}

inline int dist(int a, int b) {
    int l = lca(a, b);
    return D[a] + D[b] - 2 * D[l];
}

bool infinite(int x) {
    for (int y : F[x]) {
        if (dist(x, y) >= 3)
            return true;
    }
    return false;
}

bool isinfinite = false;
int best = 0;

int s, t;


void DFS2(int x, int p = -1, int d = 0) {
    best = max(best, dist(t, x));
    if (infinite(x)) {
        isinfinite = true;
        return;
    }
    for (int y : F[x]) {
        if (y == p)
            continue;
        if (d + 1 < dist(t, y)) {
            DFS2(y, x, d + 1);
            if (isinfinite)
                return;
        }
    }
}

int main() {
    int n;
    scanf("%d %d %d", &n, &s, &t);
    --s, --t;
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        --a, --b;
        F[a].push_back(b);
        F[b].push_back(a);
    }
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        --a, --b;
        E[a].push_back(b);
        E[b].push_back(a);
    }
    DFS(0);
    DFS2(s);
    if (isinfinite) {
        printf("%d\n", -1);
    } else {
        printf("%d\n", 2 * best);
    }
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:78:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &s, &t);
                                  ^
./Main.cpp:82:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
                               ^
./Main.cpp:89:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
                               ^

Judge Result