WA on test #7求助
查看原帖
WA on test #7求助
769456
Alexoip楼主2023/10/22 00:26
#include <bits/stdc++.h>

using namespace std;

#define LL long long
#define int long long

const int N = 1e5 + 10;

int n, m;
int u[N], v[N];
LL len[N];
vector<int> G[N];
int clk, dep[N], sz[N];
int dfn[N], fa[N][26], d[N];

int lowbit(int x) { return x & (-x); }

void add(int i, int x) {
	for (; i <= n; i += lowbit(i)) {
		len[i] = x; 
	}
}

LL sum(int i) {
	LL ret = 0;
	for (; i; i -= lowbit(i)) {
		ret += len[i]; 
	}
	return ret;
}

void dfs(int u, int p) {
	dfn[u] = ++clk, fa[u][0] = p;
	dep[u] = dep[p] + 1, sz[u] = 1;
	for (int i = 1; i < 26; i++) {
		fa[u][i] = fa[fa[u][i - 1]][i - 1];
	}
	for (int v : G[u]) {
		if (v == p) continue;
		d[v] = d[u] + 1;
		dfs(v, u);
		sz[u] += sz[v];
	}
}

int lca(int u, int v) {
	if (dep[u] < dep[v]) swap(u, v);
	for (int i = 25; i >= 0; i--) {
		if (((dep[u] - dep[v]) >> i) & 1) u = fa[u][i];
	}
	if (u == v) return u;
	for (int i = 25; i >= 0; i--) {
		if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
	}
	return fa[u][0];
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i < n; i++) {
    	cin >> u[i] >> v[i];
    	G[u[i]].push_back(v[i]);
    	G[v[i]].push_back(u[i]);
	}
	dep[1] = 1;
	dfs(1, 0);
	cin >> m;
	while (m--) {
		int op;
		cin >> op;
		if (op <= 2) {
			int i;
			cin >> i;
			if (dep[v[i]] > dep[u[i]]) {
				add(dfn[v[i]], op - 1);
				add(dfn[v[i]] + sz[v[i]], 1 - op);
			} else {
				add(dfn[u[i]], op - 1);
				add(dfn[u[i]] + sz[u[i]], 1 - op);
			}
		} else {
			int u, v;
			cin >> u >> v;
			LL dis = sum(dfn[u]) + sum(dfn[v]) - 2 * sum(dfn[lca(u, v)]);
			LL ret = d[u] + d[v] - 2 * d[lca(u, v)];
			cout << (dis >= 1 ? -1 : ret) << "\n";
		}
	} 
    return 0;
}
2023/10/22 00:26
加载中...