求助...
查看原帖
求助...
141599
sinsop90楼主2022/5/14 11:24

怎么调都是第三个点第四个数错

#include <bits/stdc++.h>
#define maxn 500005
using namespace std;
int n, head[maxn], cnt, dfn[maxn], fa[maxn], sz[maxn], dep[maxn], totp, son[maxn], top[maxn], jum[maxn][25], m, tot, T, ansn[maxn][2], anst[maxn], c[maxn << 1], lp;
struct noded {
	int v, pre;
}e[maxn << 1];
struct node {
	int x, y, p, id, ans, add;
}t[maxn << 1];
void add(int u, int v) {
	e[++cnt].v = v;
	e[cnt].pre = head[u];
	head[u] = cnt;
}
void dfs1(int now, int fat) {
	dfn[now] = ++ lp;
	fa[now] = fat;
	dep[now] = dep[fat] + 1;
	sz[now] = 1;
	int t = -1;
	for(int i = head[now];i;i = e[i].pre) {
		int v = e[i].v;
		if(v == fat) continue;
		
		dfs1(v, now);
		sz[now] += sz[v];
		if(sz[v] > t) {
			t = sz[v];
			son[now] = v;
		}
	}
}
void dfs2(int now, int tp) {
	top[now] = tp;
//	id[now] = ++ totp; 
	if(!son[now]) return;
	dfs2(son[now], tp);
	for(int i = head[now];i;i = e[i].pre) {
		int v = e[i].v;
		if(v != fa[now] && v != son[now]) dfs2(v, v);
	}
}
int find(int x, int y) {
	while(top[x] != top[y]) {
		if(dep[top[x]] < dep[top[y]]) swap(x, y);
		x = fa[top[x]];
	}
	if(dep[x] > dep[y]) return y;
	return x;
}
void dfs3(int now) {
	for(int i = head[now];i;i = e[i].pre) {
		int v = e[i].v;
		if(v == fa[now]) continue;
		dfs3(v);
		if(dep[jum[v][0]] < dep[jum[now][0]]) jum[now][0] = jum[v][0];
	}
}
bool cmp(node a, node b) {
	if(a.x < b.x) return true;
	if(a.x > b.x) return false;
	if(a.y < b.y) return true;
	if(a.y > b.y) return false;
	if(a.p < b.p) return true;
	return false;
}
int lowbit(int x) {
	return x & (-x);
}
void adde(int x) {
	while(x <= 510000) {
		c[x] ++;
		x += lowbit(x);
	}
}
int query(int x) {
	int res = 0;
	while(x) {
		res += c[x];
		x -= lowbit(x);
	}
	return res;
}
int main() {
	scanf("%d", &n);
	for(int i = 2;i <= n;i++) {
		int x;
		scanf("%d", &x);
		add(i, x);
		add(x, i);
	}
	dfs1(1, 0);
	dfs2(1, 1);
	for(int i = 1;i <= n;i++) jum[i][0] = i;
	dep[0] = 21474866;
	scanf("%d", &m);
	for(int i = 1;i <= m;i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		int lca = find(u, v);
		if(dep[lca] < dep[jum[u][0]]) jum[u][0] = lca;
		if(dep[lca] < dep[jum[v][0]]) jum[v][0] = lca;
		t[++tot].x = dfn[u] + 1;
		t[tot].y = dfn[v] + 1;
		t[tot].p = 0;
		t[++tot].x = dfn[v] + 1;
		t[tot].y = dfn[u] + 1;
		t[tot].p = 0;
	}
	dfs3(1);
	for(int i = 1;i <= n;i++) jum[i][0] = (jum[i][0] == i) ? 0 : jum[i][0];
	for(int i = 1;i <= 24;i++) {
		for(int j = 1;j <= n;j++) {
			jum[j][i] = jum[jum[j][i - 1]][i - 1];
		}
	}
	scanf("%d", &T);
	for(int i = 1;i <= T;i++) {
		int x, y, ans = 0;
		scanf("%d%d", &x, &y);
		int lca = find(x, y);
//		cout << jum[y][0] << endl;
		for(int j = 20;j >= 0;j--) {
			if(dep[jum[x][j]] > dep[lca] && jum[x][j]) {
				x = jum[x][j];
				ans += (1 << j);
			}
		}
		for(int j = 20;j >= 0;j--) {
			if(dep[jum[y][j]] > dep[lca] && jum[y][j]) {
				y = jum[y][j];
				ans += (1 << j);
			}
		}
		if(x == lca || y == lca) {
			if(y == lca) swap(x, y);
			if(dep[jum[y][0]] <= dep[x]) {
				
				ansn[i][0] ++;
			}
			else ansn[i][0] = -1;
		}
		else {
			if((!jum[x][0]) || (!jum[y][0]) || (dep[lca] < dep[jum[x][0]]  && jum[x][0] && dep[lca] < dep[jum[y][0]] && jum[y][0])) {
				ansn[i][0] = -1;
				continue;
			}
//			cout << x << " " << y << " " << ans << endl;
			ansn[i][0] = ans + 2;
			int a = dfn[x], b = dfn[y], c = dfn[x] + sz[x] - 1, d = dfn[y] + sz[y] - 1;
			a ++, b ++, c ++, d ++;
			t[++tot].x = a - 1;
			t[tot].y = b - 1;
			t[tot].p = 1;
			t[tot].add = 1;
			t[tot].id = i;
			t[++tot].x = c;
			t[tot].y = d;
			t[tot].p = 1;
			t[tot].add = 1;
			t[tot].id = i;
			t[++tot].x = a - 1;
			t[tot].y = d;
			t[tot].p = 1;
			t[tot].add = -1;
			t[tot].id = i;
			t[++tot].x = c;
			t[tot].y = b - 1;
			t[tot].p = 1;
			t[tot].add = -1;
			t[tot].id = i;
		}
	}
	sort(t + 1, t + 1 + tot, cmp);
	for(int i = 1;i <= tot;i++) {
		if(t[i].p == 0) {
			adde(t[i].y);
		}
		else {
			anst[t[i].id] += query(t[i].y) * t[i].add;
		}
	}
	for(int i = 1;i <= T;i++) {
			if(anst[i]) ansn[i][0] --;
			printf("%d\n", ansn[i][0]);
	}
}
2022/5/14 11:24
加载中...