@[Skadi_H](/user/1006027) 我在合适的地方(edge上面会卡不过去)jialege`#define int long long`就过了
```cpp
#include <bits/stdc++.h>
using namespace std;
struct edge
{
int v,w,nxt;
}e[600005];
#define int long long
int n,m,u,v,w,pos,lca,l,r,mid,res,cnt,maxn,maxv,acnt,pcnt;
int dis[300005],head[300005],st[300005][25],dep[300005],data[300005][2],ans[300005],d[300005][35],s[300005];
unordered_map<long long,int>ma,id;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
inline void write(int x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
write(x/10);
putchar(x%10+'0');
}
inline void addedge(int u,int v,int w)
{
e[++pos]={v,w,head[u]};
head[u]=pos;
}
inline void dfs1(int u,int fa=0)
{
dis[u]=dis[fa]+ma[u*1000000+fa];
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa)
continue;
dfs1(v,u);
}
}
inline void dfs2(int u,int fa=0)
{
st[u][0]=fa;
dep[u]=dep[fa]+1;
for(int i=1;i<=__lg(dep[u]);i++)
{
st[u][i]=st[st[u][i-1]][i-1];
}
for(int i=head[u];i;i=e[i].nxt)
{
if(e[i].v!=fa)
dfs2(e[i].v,u);
}
}
inline int LCA(int u,int v)
{
if(dep[u]<dep[v])
swap(u,v);
while(dep[u]!=dep[v])
{
u=st[u][__lg(dep[u]-dep[v])];
}
if(u==v)
return u;
for(int i=__lg(dep[u]);i>=0;i--)
{
if(st[u][i]!=st[v][i])
{
u=st[u][i];
v=st[v][i];
}
}
return st[u][0];
}
inline void dfs3(int u,int fa,int t,int pcnt)
{
s[u]=d[u][t];
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa)
continue;
dfs3(v,u,t,pcnt);
s[u]+=s[v];
if(s[v]==pcnt)
{
acnt++;
maxv=max(maxv,ma[u*1000000+v]);
}
}
}
inline bool check(int x,int t)
{
maxn=0,pcnt=0;
for(int i=1;i<=m;i++)
{
if(ans[i]<=x)
continue;
maxn=max(maxn,ans[i]);
pcnt++;
int u=data[i][0],v=data[i][1];
d[u][t]++;
d[v][t]++;
d[LCA(u,v)][t]-=2;
}
acnt=0,maxv=0;
dfs3(1,0,t,pcnt);
if(acnt==0||maxn-maxv>x)
return false;
return true;
}
main(){
std::ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
n=read();m=read();
for(int i=1;i<n;i++)
{
u=read();v=read();w=read();
addedge(u,v,w);
addedge(v,u,w);
ma[u*1000000+v]=ma[v*1000000+u]=w;
id[u*1000000+v]=id[v*1000000+u]=i;
}
dfs1(1);
dfs2(1);
for(int i=1;i<=m;i++)
{
u=read();v=read();
data[i][0]=u,data[i][1]=v;
lca=LCA(u,v);
ans[i]=dis[u]+dis[v]-2*dis[lca];
r=max(r,ans[i]);
}
res=r;
while(l<=r)
{
mid=l+r>>1;
if(check(mid,++cnt))
{
res=mid;
r=mid-1;
}
else
l=mid+1;
}
write(res);
return 0;
}
//[Skadi_H](/user/1006027)
```
by 赛克尔だよ @ 2023-10-16 23:11:50
加了个
by 赛克尔だよ @ 2023-10-16 23:12:11
@[赛克尔だよ](/user/376348) 昨天晚上休息的比较早,现在才看到,不好意思
现在已经过了!
**sto 感谢巨佬 orz**
by Skadi_H @ 2023-10-17 12:12:46
受巨佬启发,发现这是我个人写法的一个问题
```cpp
ma[u*1000000+v]=ma[v*1000000+u]=w;
改为
ma[1ll*u*1000000+v]=ma[1ll*v*1000000+u]=w;
```
在里面乘的时候乘爆了QaQ
by Skadi_H @ 2023-10-17 12:15:04
**此贴完结**
by Skadi_H @ 2023-10-17 18:10:13