6分re mle tle 什么东西啊()
查看原帖
6分re mle tle 什么东西啊()
389540
imfkwk楼主2021/2/6 00:48

附上从loj抄风格的代码(大错误

#include <bits/stdc++.h>
#define int long long
#define N 50005
using namespace std;

void read(int& x) {
	x = 0;
	int f = 1;
	
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-') f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 1) + (x << 3) + ch^48;
		ch = getchar();
	}
	
	x = f * x;
}

void write(int x) {
	if (x < 0) {
		putchar('-');
		x = -x;
	}
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}

int head[N];
int from[N<<1];
int to[N<<1]; 
int cnt;

void build(int x, int y) {
	++cnt;
	from[cnt] = head[x];
	to[cnt] = y;
	head[x] = cnt;
}

int f[N][21];
int d[N];

void dfs1(int node) {
	for (int i = 1; i <= 20; ++i) {
		f[node][i] = f[f[node][i - 1]][i - 1];
	}
	
	for (int p = head[node]; p; p = from[p]) {
		int t = to[p];
		if (t != f[node][0]) {
			f[t][0] = node;
			d[t] = d[node] + 1;
			dfs1(t);
		}
	}
}

int lca(int x, int y) {
	if (d[x] < d[y]) swap(x, y);
	int c = d[x] - d[y];
	
	for (int i = 20; i >= 0; --i) {
		if (c & (1 << i)) x = f[x][i];
		if (x == y) return x;
	}
	
	for (int i = 20; i >= 0; --i) {
		if (f[x][i] != f[y][i]) {
			x = f[x][i];
			y = f[y][i];
		}
	}
	
	return f[x][0];
}

int sum[N];
int ans;

void dfs2(int node) {
	for (int p = head[node]; p; p = from[p]) {
		int t = to[p];
		if (t != f[node][0]) {
			dfs2(t);
			sum[node] += sum[t];
		}
	}
	ans = max(ans, sum[node]);
}

int n, k;

signed main(void) {
	read(n); read(k);
	
	for (int i = 1; i <= n - 1; ++i) {
		int x, y;
		read(x); read(y);
		build(x, y);
		build(y, x);
	}
	
	d[1] = 1;
	dfs1(1);
	
	for (int i = 1; i <= k; ++i) {
		int x, y;
		read(x); read(y);
		++sum[x];
		++sum[y];
		--sum[lca(x, y)];
		--sum[f[lca(x, y)][0]];
	}
	
	dfs2(1);
	
	write(ans);
	
	return 0;
}
2021/2/6 00:48
加载中...