树剖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
函数名和某题解可能有点像,因为蒟蒻是看了题解自学树剖才来切题的