C++14(g++5.4) 解法, 执行用时: 1593ms, 内存消耗: 48604K, 提交时间: 2020-03-09 16:56:50

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define maxn 300005
using namespace std;
struct yyy{int t,nex,cost;}e[2*maxn];
int depth[maxn]={0},fa[maxn][22]={0},lg[maxn]={0},head[maxn];//数组depth表示每个节点的深度，fa[i][j]表示节点i的2j级祖先 
int tot;
int dis[maxn];
void add(int x,int y,int z)
{
    e[++tot].t=y; 
    e[tot].nex=head[x];
    e[tot].cost=z;
    head[x]=tot;
}
vector<int>seq;
void dfs(int p,int fath,int cost)
{
	seq.push_back(p);
	dis[p]=dis[fath]+cost;
    depth[p]=depth[fath]+1;
    fa[p][0]=fath;
    for(int i=1;(1<<i)<=depth[p];i++)
      fa[p][i]=fa[fa[p][i-1]][i-1];
    for(int i=head[p];i;i=e[i].nex)
      if(e[i].t!=fath)
        dfs(e[i].t,p,e[i].cost);
}
int lca(int x,int y)
{
    if(depth[x]<depth[y])
      swap(x,y);
    for(int i=0;i<22;i++)if((depth[x]-depth[y])&(1<<i))x=fa[x][i];
	if(x==y)
      return x;
    for(int k=lg[depth[x]]-1;k>=0;k--)
      if(fa[x][k]!=fa[y][k])
        x=fa[x][k], y=fa[y][k];
    return fa[x][0];
}
int n,m;
int u[maxn],v[maxn],LCA[maxn];
int sum[maxn];
bool check(int x)
{
	memset(sum,0,sizeof(sum));
	int maxd=0,cnt=0;
	for (int i=0;i<m;i++)
	{
		int d=dis[u[i]]+dis[v[i]]-2*dis[LCA[i]];
		if (d>x)
		{
			sum[u[i]]++,sum[v[i]]++,sum[LCA[i]]-=2;
			cnt++;
			maxd=max(maxd,d-x);
		}
	}
	if (!cnt) return 1;
	for (int i=seq.size()-1;i>0;i--)
	{
		int p=seq[i];
		sum[fa[p][0]]+=sum[p];
	}
	for (int i=2;i<=n;i++)
	{
		if (sum[i]==cnt&&dis[i]-dis[fa[i][0]]>=maxd)
		return 1;
	}
	return 0;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n-1;i++)
    {
        int x,y,z;  scanf("%d%d%d",&x,&y,&z);
        add(x,y,z); add(y,x,z);
    }
    dfs(1,0,0);
    for(int i=1;i<=n;i++)
      lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    for (int i=0;i<m;i++)
    {
    	scanf("%d%d",&u[i],&v[i]);
    	LCA[i]=lca(u[i],v[i]);
	}
	int le=0,ri=1e9,ans;
	while(le<=ri)
	{
		int mid=(le+ri)/2;
		if (check(mid))
		{
			ri=mid-1;
			ans=mid;
		}
		else le=mid+1;
	}
	printf("%d",ans);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 363ms, 内存消耗: 28380K, 提交时间: 2020-03-04 14:58:14

#include<bits/stdc++.h>
using namespace std;
const int NN=3e5+4;
struct edge
{
	int nxt,to,w;
}e[NN<<1];
struct node
{
	int x,y,lca,d;
}a[NN];
int fa[NN],h[NN],siz[NN],son[NN],top[NN],dfn[NN],head[NN],w[NN],num[NN],dis[NN],tim,tot,n,m,maxl=0,maxr=0;
void add(int x,int y,int z)
{
	e[++tot].nxt=head[x];
	e[tot].to=y;
	e[tot].w=z;
	head[x]=tot;
}
void dfs1(int u)
{
	h[u]=h[fa[u]]+1;
	siz[u]=1;
	int v;
	for(int i=head[u];i;i=e[i].nxt)
	if((v=e[i].to)!=fa[u])
	{
		fa[v]=u;
		w[v]=e[i].w;
		dis[v]=dis[u]+e[i].w;
		dfs1(v);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]])
		son[u]=v;
	}
}
void dfs2(int u,int tp)
{
	top[u]=tp;
	dfn[++tim]=u;
	if(son[u])
	dfs2(son[u],tp);
	int v;
	for(int i=head[u];i;i=e[i].nxt)
	if((v=e[i].to)!=fa[u]&&v!=son[u])
	dfs2(v,v); 
}
int lca(int l,int r)
{
	while(top[l]!=top[r])
	{
		if(h[top[l]]<h[top[r]])
		swap(l,r);
		l=fa[top[l]];
	}
	return h[l]<=h[r]?l:r;
}
int check(int mid)
{
	int sum=0;
	memset(num,0,sizeof(num));
	for(int i=1;i<=m;i++)
	if(a[i].d>mid)
	{
		num[a[i].x]++;
		num[a[i].y]++;
		num[a[i].lca]-=2;
		sum++;
	 } 
	 for(int i=n;i>=1;i--)
	 {
	 	num[fa[dfn[i]]]+=num[dfn[i]];
	 	if(w[dfn[i]]>=maxr-mid&&num[dfn[i]]==sum)
	 	return 1;
	 }
	 return 0;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
		maxl=max(maxl,z);
	}
	dfs1(1);
	dfs2(1,1);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&a[i].x,&a[i].y);
		a[i].lca=lca(a[i].x,a[i].y);
		a[i].d=dis[a[i].x]+dis[a[i].y]-2*dis[a[i].lca];
		maxr=max(maxr,a[i].d);
	}
	int l=maxr-maxl,r=maxr+1;
	while(l<r)
	{
		int mid=(l+r)>>1;
		if(check(mid))
		r=mid;
		else
		l=mid+1;
	}
	printf("%d",l);
	return 0;
}