记录编号	540462	评测结果	AAAAAAAAAA
题目名称	[SYOI 2019] 探险	最终得分	100
用户昵称	ShallowDream雨梨	是否通过	通过
代码语言	C++	运行时间	0.114 s
提交时间	2019-08-24 12:31:19	内存使用	11.42 MiB

#include <bits/stdc++.h>
using namespace std;
const int maxn=200005;
int qwq,ans,sum[maxn],e,tot,head[maxn];
int tree_f[maxn],lg[maxn],dep[maxn],f[maxn][22];
struct tree1{int from,to,v;}tree[maxn];
int cmp(tree1 q,tree1 w){return q.v<w.v;}
inline int read()
{
     int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}
struct road{int to,next;}a[maxn];
int find(int x){
	if(tree_f[x]!=x)
	tree_f[x]=find(tree_f[x]);
	return tree_f[x];
}
void add(int x,int y){
	tot++;a[tot].to=y;
	a[tot].next=head[x];head[x]=tot;}
void dfs(int x,int fa){
	f[x][0]=fa;
	dep[x]=dep[fa]+1;
	for(int i=1;(1<<i)<=dep[x];i++)
	f[x][i]=f[f[x][i-1]][i-1];
	for(int i=head[x];i;i=a[i].next){
		int to=a[i].to;
		if(to!=fa)dfs(to,x);}}
int lca(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	while(dep[x]>dep[y]){
		x=f[x][lg[dep[x]-dep[y]]-1];}
	if(x==y)return x;
	for(int i=lg[dep[x]];i>=0;i--){
	if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];}
	return f[x][0];}	
	
void dfs2(int x,int fa){
	for(int i=head[x];i;i=a[i].next){
		if(a[i].to!=fa){
		dfs2(a[i].to,x);
		sum[x]+=sum[a[i].to];}}
return;}
int Main(){
	freopen("tanxia.in","r",stdin);
	freopen("tanxia.out","w",stdout);
	int n,m,k;//n_dian m_bian k_tanxian
	int fq,fw,q,w;
	n=read();m=read();k=read();
	for(int i=1;i<=n;i++)tree_f[i]=i;
	for(int i=1;i<=m;i++){
		q=read();w=read();e=read();
		tree[i].from=q;
		tree[i].to=w;
		tree[i].v=e;}cout<<endl;
	sort(tree+1,tree+1+m,cmp);
	for(int i=1;i<=m;i++){
		q=tree[i].from;w=tree[i].to;
	 fq=find(q),fw=find(w);
	if(fq==fw)continue;
	tree_f[fw]=fq;
		add(q,w);
		add(w,q);}
	for(int i=1;i<=n;i++)
	lg[i]=lg[i-1]+(i==1<<(lg[i-1]));
	dfs(1,0);
	for(int i=1;i<=k;i++){
		q=read();w=read();
		e=lca(q,w);
		sum[e]--;sum[f[e][0]]--;sum[q]++;sum[w]++;}
	dfs2(1,0);
	for(int i=1;i<=n;i++){
		if(sum[i]>=ans){
			qwq=i;
		if(sum[i]>ans)
			ans=sum[i];	}}
	cout<<qwq<<' '<<ans;
   return 0;
}
int qwqq=Main();
int main(){;}