第一个点AC,其余WA+TLE求调
查看原帖
第一个点AC,其余WA+TLE求调
744853
FChang楼主2024/1/23 21:30
#include <bits/stdc++.h>
#define intt register int
#define ll long long
using namespace std;
const int N = 1e5 + 10;

int n,k;
int dep[N],fa[N],siz[N],son[N],l[N],lcnt,lsum[N],sum[N],lt[N];

int head[N],cnt = 1;
struct edge{
	int to,next;
}a[N];

void edg(int u,int v) {
	a[cnt].to = v;
	a[cnt].next = head[u];
	head[u] = cnt++;
}

void dfs1(int x,int father) {
	fa[x] = father;
	dep[x] = dep[father] + 1;
	siz[x] = 1;
	for(intt i=head[x];i;i=a[i].next) {
		int v = a[i].to;
		if(v==father || fa[v]) continue;
		dfs1(v,x);
		siz[x] += siz[v];
		if(siz[v]>siz[son[x]]) son[x] = v;
	}
	return ;
}

void dfs2(int x,int p) {
	if(p>0) lt[x] = p;
	for(intt i=head[x];i;i=a[i].next) {
		int v = a[i].to;
		if(lt[v]) continue;
		if(v==son[x]) dfs2(v,p);
		else l[++lcnt] = v,dfs2(v,v);
	}
	return ;
}

void q(int x,int y) {
	while(lt[x]!=lt[y]) {
		if(dep[x] < dep[y]) swap(x,y);
		lsum[lt[x]]++;
		x = fa[lt[x]];
	}
	while(x!=y) {
		if(dep[x] < dep[y]) swap(x,y);
		sum[x]++;
		x = fa[x];
	}
	sum[x]++;
	return ;
}

int main() {
	ios::sync_with_stdio(0);
	ios_base::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);
	cin>>n>>k;
	int u,v;
	for(intt i=1;i<n;++i) {
		cin>>u>>v;
		edg(u,v);edg(v,u);
	}
	lt[1] = 1;
	dfs1(1,1);
	dfs2(1,1);
	for(intt i=1;i<=k;i++) {
		cin>>u>>v;
		q(u,v);
	}
	int mn = -1;
	for(intt i=1;i<=n;i++)
		mn = max(mn,sum[i]+lsum[lt[i]]);
	cout<<mn<<" ";
	return 0;
}
2024/1/23 21:30
加载中...