求大佬们帮帮忙,行行好QAQ蒟蒻真的看不出来
查看原帖
求大佬们帮帮忙,行行好QAQ蒟蒻真的看不出来
218051
emiermao楼主2020/8/12 10:36

树剖RE了,不知道为啥(应该是段错误,可我实在看不出哪里数组开小了,翻了一倍也RE)

#include <bits/stdc++.h>
using namespace std;
int par[1005], son[1005], head[1005];
struct Node {
        int to;
        int next;
}edge[1005];
int ind = 0;
void add (int fa, int v) {
        par[v] = fa;
        edge[ind].to = v;
        edge[ind].next = head[fa];
        head[fa] = ind++;
        return;
}
int top[1005], size[1005], dep[1005];
int root;
void dfs1 (int x) {
        //printf("%d\n", x);
        size[x] = 1;
        dep[x] = dep[par[x]] + 1;
        int maxson = -1;
        for (int i = head[x]; i != -1; i = edge[i].next) {
                dfs1(edge[i].to);
                size[x] += size[edge[i].to];
                if (maxson == -1 || size[maxson] < size[edge[i].to]) {
                        maxson = edge[i].to;
                }
        }
        son[x] = maxson;
        return;
}
void dfs2 (int x, int t) {
        //printf("%d\n", x);
        top[x] = t;
        if (son[x] == -1) {
                return;
        }
        dfs2(son[x], t);
        for (int i = head[x]; i != -1; i = edge[i].next) {
                if (edge[i].to != son[x])
                        dfs2(edge[i].to, edge[i].to);
        }
        return;
}
int query (int x, int y) {
        while (top[x] != top[y]) {
                if (dep[top[x]] < dep[top[y]]) {
                        swap(x, y);
                }
                x = par[top[x]];
        }
        if (dep[x] < dep[y]) {
                return x;
        }else {
                return y;
        }
}
int main () {
        int t;
        scanf("%d", &t);
        for (int temp = 1; temp <= t; temp++) {
            printf("Case %d:\n", temp);
            memset(head, -1, sizeof(head));
            memset(par, 0, sizeof(par));
            memset(top, 0, sizeof(top));
            memset(size, 0, sizeof(size));
            memset(dep, 0, sizeof(dep));
            int n;
            scanf("%d", &n);
            for (int i = 1; i <= n; i++) {
                    int m;
                    scanf("%d", &m);
                    while (m--) {
                            int s;
                            scanf("%d", &s);
                            add(i, s);
                    }
            }
            for (int i = 1; i <= n; i++) {
                    if (!par[i]) {
                            root = i;
                            break;
                    }
            }
            dfs1(root);
            dfs2(root, root);
            int q;
            //printf("%d %d\n", top[5], top[7]);
            scanf("%d", &q);
            while (q--) {
                    int u, v;
                    scanf("%d %d", &u, &v);
                    printf("%d\n", query(u, v));
            }
        }
        return 0;
}

又及:

我一气之下把另一道题的AC代码copy过来,完美WA

函数名和某题解可能有点像,因为蒟蒻是看了题解自学树剖才来切题的

2020/8/12 10:36
加载中...