神奇的错误,WA #1#4#7
查看原帖
神奇的错误,WA #1#4#7
549846
dpACerFXing楼主2023/10/27 11:17
# include<iostream>
# include<cmath>
# include<algorithm>
# include<vector>
using namespace std;
const int maxn=101;
struct Node{
	int u, v, next;
}edge[maxn*2];
int n, head[maxn], cnt=0, f[maxn][21], dep[maxn], ton[maxn], depth, width;
vector<int> son[maxn];
void add(int u, int v) {
	cnt++;
	edge[cnt].u=u;
	edge[cnt].v=v;
	edge[cnt].next=head[u];
	head[u]=cnt;
}
void dfs(int p, int fa) {
	for(int i=head[p]; i; i=edge[i].next) {
		int v=edge[i].v;
		if(v==fa) continue;
		f[v][0]=p;
		son[p][0]++;
		son[p].push_back(v); 
		dep[v]=dep[p]+1;
		depth=max(depth, dep[v]);
		ton[dep[v]]++;
		width=max(width, ton[dep[v]]);
		dfs(v, p);
	}
}
int main() {
	cin >> n;
	for(int i=1; i<=n; i++) {
		son[i].push_back(0);
	}
	for(int i=1; i<=n-1; i++) {
		int x, y; cin >> x >> y;
		add(x, y); add(y, x);
	}
	dep[1]=1;
	dfs(1, 0);
	for(int i=1; i<=15; i++)
		for(int j=1; j<=n; j++)
			f[j][i]=f[f[j][i-1]][i-1];
	int ou, ov, u, v; cin >> ou >> ov; u=ou; v=ov;
	if(dep[u]<dep[v]) swap(u, v);
	if(dep[u]>dep[v]) {
		for(int i=15; i>=0; i--) {
			int t=f[u][i];
			if(dep[t]>=dep[v]) u=t;
		}
	}
	for(int i=15; i>=0; i--) {
		int uu=f[u][i], vv=f[v][i];
		if(uu!=vv) {
			u=uu;
			v=vv;
		}
	}
	cout << depth << endl << width << endl;
	int lca=f[u][0];
	cout << dep[ou]*2+dep[ov]-dep[lca]*3 << endl;
	return 0;
}
2023/10/27 11:17
加载中...