答案与解析
正确答案:<p style="text-align: left;">#include <bits/stdc++.h></p><p style="text-align: left;">using namespace std;</p><p> </p><p style="text-align: left;">const int Max=300005;</p><p style="text-align: left;">int n,m,s,ans,tot,l,r,mid;</p><p style="text-align: left;">int first[Max],son[Max],pos[Max],top[Max],depth[Max],father[Max],size[Max],dis[Max],num[Max],len[Max],val[Max],v[Max];</p><p style="text-align: left;">struct shu{int to,next,len;}edge[Max<<1];</p><p style="text-align: left;">struct bian{int x,y,len;}d[Max];</p><p style="text-align: left;">inline int get_int()</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>int x=0,f=1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>char c;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar());</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(c=='-') f=-1,c=getchar();</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';</p><p style="text-align: left;"><span style="white-space:pre"> </span>return x*f;</p><p style="text-align: left;">}</p><p style="text-align: left;">inline void build(int x,int y,int z){edge[++s].next=first[x],first[x]=s,edge[s].to=y,edge[s].len=z;}</p><p style="text-align: left;">inline void dfs1(int point,int fa)</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>size[point]=1,father[point]=fa,depth[point]=depth[fa]+1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int u=first[point];u;u=edge[u].next)</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span> int to=edge[u].to;</p><p style="text-align: left;"><span style="white-space:pre"> </span> if(to==fa) continue;</p><p style="text-align: left;"><span style="white-space:pre"> </span> val[to]=edge[u].len,dis[to]=dis[point]+edge[u].len;</p><p style="text-align: left;"><span style="white-space:pre"> </span> dfs1(to,point);</p><p style="text-align: left;"><span style="white-space:pre"> </span> size[point]+=size[to];</p><p style="text-align: left;"><span style="white-space:pre"> </span> if(size[to] > size[son[point]]) son[point]=to;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;">}</p><p style="text-align: left;">inline void dfs2(int point,int fa)</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(son[point])</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span> pos[son[point]]=++tot,len[tot]=val[son[point]],top[son[point]]=top[point];</p><p style="text-align: left;"><span style="white-space:pre"> </span> dfs2(son[point],point);</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int u=first[point];u;u=edge[u].next)</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span> int to=edge[u].to;</p><p style="text-align: left;"><span style="white-space:pre"> </span> if(top[to]) continue;</p><p style="text-align: left;"><span style="white-space:pre"> </span> pos[to]=++tot,top[to]=to;</p><p style="text-align: left;"><span style="white-space:pre"> </span> dfs2(to,point);</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;">}</p><p style="text-align: left;">inline int LCA(int x,int y)</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(top[x]!=top[y])</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span> if(depth[top[x]] < depth[top[y]]) x^=y,y^=x,x^=y;</p><p style="text-align: left;"><span style="white-space:pre"> </span> x=father[top[x]];</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(depth[x] > depth[y]) swap(x,y);</p><p style="text-align: left;"><span style="white-space:pre"> </span>return x;</p><p style="text-align: left;">}</p><p style="text-align: left;">inline bool comp(const bian &a,const bian &b){return a.len>b.len;}</p><p style="text-align: left;">inline void solve(int x,int y)</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(top[x]!=top[y])</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span> if(depth[top[x]] < depth[top[y]]) x^=y,y^=x,x^=y;</p><p style="text-align: left;"><span style="white-space:pre"> </span> num[pos[top[x]]+1]++,num[pos[x]+1]--;</p><p style="text-align: left;"><span style="white-space:pre"> </span> x=father[top[x]];</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(x==y) return;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(depth[x] > depth[y]) x^=y,y^=x,x^=y;</p><p style="text-align: left;"><span style="white-space:pre"> </span>num[pos[x]+1]++,num[pos[y]+1]--;</p><p style="text-align: left;">}</p><p style="text-align: left;">inline int mx(int x,int y){return x < y ? y : x;}</p><p style="text-align: left;">inline int check(int mid)</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>int k=0,x=0,sum=0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(d[k+1].len>mid) k++;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(v[k]) return v[k];</p><p style="text-align: left;"><span style="white-space:pre"> </span>memset(num,0,sizeof(num));</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=1;i<=k;i++) solve(d[i].x,d[i].y);</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=1;i<=n;i++){sum+=num[i];if(sum == k) x=mx(x,len[i]);}</p><p style="text-align: left;"><span style="white-space:pre"> </span>v[k]=x;</p><p style="text-align: left;"><span style="white-space:pre"> </span>return x;</p><p style="text-align: left;">}</p><p style="text-align: left;">inline void print(int x){if(x>9) print(x/10);putchar('0'+x%10);}</p><p style="text-align: left;">int main()</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>n=get_int(),m=get_int();</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=1;i<=n-1;i++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span> int x=get_int(),y=get_int(),z=get_int();</p><p style="text-align: left;"><span style="white-space:pre"> </span> build(x,y,z),build(y,x,z);</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>top[1]=tot=pos[1]=1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>dfs1(1,0),dfs2(1,0);</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=1;i<=m;i++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span> d[i].x=get_int(),d[i].y=get_int();</p><p style="text-align: left;"><span style="white-space:pre"> </span> d[i].len=dis[d[i].x]+dis[d[i].y]-2*dis[LCA(d[i].x,d[i].y)];</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>sort(d+1,d+m+1,comp);</p><p style="text-align: left;"><span style="white-space:pre"> </span>l=0,r=d[1].len;</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(l<r)</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span> mid=(l+r)>>1;</p><p style="text-align: left;"><span style="white-space:pre"> </span> (d[1].len - check(mid) <= mid) ? r=mid : l=mid+1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>print(r);</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。