记录编号	540461	评测结果	AAAAAAAAAA
题目名称	[SYOI 2019] 探险	最终得分	100
用户昵称	Hale	是否通过	通过
代码语言	C++	运行时间	0.167 s
提交时间	2019-08-24 11:50:36	内存使用	137.64 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+7;
int m,n,k,p,ans,mx,tot;
int fa[N],dep[N],size[N],son[N],f[N],top[N],v[N],cnt,head[N];
bool vis[N];
int find(int x)
{
	if (f[x]!=x) return f[x]=find(f[x]);
	return f[x];
}
inline int read()
{
    int x=0,t=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return x*t;
}
struct edge
{
	int nx,to,dist,from;
	bool operator <(const edge &x ) const
	{
		return dist<x.dist;
	}
} e[N],a[N];
void add_edge(int a,int b)
{
	cnt++;e[cnt].nx=head[a];e[cnt].to=b;head[a]=cnt;
}
void dfs1(int x,int ff,int deep)
{
	size[x]=1;fa[x]=ff;dep[x]=deep;
	for (int i=head[x];i;i=e[i].nx)
	{
		int y=e[i].to;
		if (y==ff) continue;
		dfs1(y,x,deep+1);
		size[x]+=size[y];
		if (size[y]>size[son[x]]) son[x]=y;
	}
}
void dfs2(int x,int topf)
{
	top[x]=topf;
	if (!son[x]) return;
	dfs2(son[x],topf);
	for (int i=head[x];i;i=e[i].nx)
	{
		int y=e[i].to;
		if (y==son[x]||y==fa[x]) continue;
		dfs2(y,y);
	}
}
int get_lca(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]) swap(x,y);
	return x;
}
void dfs(int x)
{
	for (int i=head[x];i;i=e[i].nx)
	{
		int y=e[i].to;
		if (y==fa[x]) continue;
		dfs(y);
		v[x]+=v[y];
	}
	if (v[x]>ans) {ans=v[x],mx=x;}
	if (v[x]==ans) {mx=max(mx,x);}
}
int main()
{
	freopen("tanxia.in","r",stdin);
	freopen("tanxia.out","w",stdout);
	n=read(),m=read();int Q=read();
	for (int i=1;i<=m;i++) a[i].from=read(),a[i].to=read(),a[i].dist=read();
	sort(a+1,a+m+1); for (int i=1;i<=n;i++) f[i]=i;
	for (int i=1;i<=m;i++)
	{
		int x=a[i].from,y=a[i].to,z=a[i].dist;
		int fx=find(x),fy=find(y);
		if (find(x)!=find(y)) add_edge(x,y),f[fx]=fy,tot++,add_edge(y,x);
		if (tot==n-1) break;
	}
	dfs1(1,0,1);dfs2(1,1);
	while (Q--)
	{
		int x=read(),y=read();int lc=get_lca(x,y);
		v[x]++;v[y]++;v[lc]--;v[fa[lc]]--;
	}
	dfs(1);
	printf("%d %d\n",mx,ans);
	return 0;
}