~~CO 批差不多得了~~
by QAQ__ @ 2023-05-14 23:06:45
@[QAQ__](/user/627636) （
我超，乱改一通变成70pts（
再放一遍代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
struct edge{int nex,val;};
int n,m,f[25][N],dep[N],d[N],c[N],B[N],E[N],len[N],LCA[N],res;
vector<edge>e[N];
void dfs(int u,int t)
{
dep[u]=dep[t]+1;
for(int i=1;(1<<i)<=dep[u];i++)f[i][u]=f[i-1][f[i-1][u]];
for(auto x:e[u])if(x.nex!=t)f[0][x.nex]=u,d[x.nex]=d[u]+x.val,dfs(x.nex,u);
return;
}
int lca(int x,int y)
{
if(dep[x]<dep[y])swap(x,y);
for(int i=20;i>=0;i--){if(dep[f[i][x]]>=dep[y])x=f[i][x];if(x==y)return x;}
for(int i=20;i>=0;i--)if(f[i][x]!=f[i][y])x=f[i][x],y=f[i][y];
return f[0][x];
}
int dis(int x,int y)
{
return d[x]+d[y]-(d[lca(x,y)]<<1);
}
void DFS(int u,int t,int P)
{
for(auto x:e[u])
{
int v=x.nex;
if(v==t)continue;
DFS(v,u,P);
if(c[v]+c[u]==P&&x.val>res)res=x.val;
}
for(auto x:e[u])c[u]+=c[x.nex];
return;
}
bool check(int h)
{
vector<int>q;
memset(c,0,sizeof(c));res=-1e9;
for(int i=1;i<=m;i++)if(len[i]>h)q.push_back(i);
for(int i:q)c[B[i]]++,c[E[i]]++,c[f[0][LCA[i]]]-=2;
DFS(1,0,q.size());
for(int i=1;i<=n;i++)if(len[i]-res>h)return 0;
return 1;
}
void search(int l,int r)
{
if(l>=r){printf("%d\n",l);return;}
int mid=l+r>>1;
if(check(mid))search(l,mid);
else search(mid+1,r);
return;
}
signed main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
e[x].push_back({y,z});e[y].push_back({x,z});
}
dfs(1,0);
int Max=-1e9;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&B[i],&E[i]);
Max=max(Max,len[i]=dis(B[i],E[i]));
LCA[i]=lca(B[i],E[i]);
}
search(0,Max);
return 0;
}
```
by Sheez @ 2023-05-14 23:11:22
因为或许 下个路口仍是同样的结局
by zhy137036 @ 2023-05-15 07:37:58
不存在刹那的奇迹
by QAQ__ @ 2023-05-15 08:40:22
草两个金钩
by Sheez @ 2023-05-15 08:53:28
过了过了
`DFS` 函数应改为：
```cpp
void DFS(int u,int t,int P)
{
for(auto x:e[u])
{
int v=x.nex;
if(v==t)continue;
DFS(v,u,P);c[u]+=c[v];
if(c[v]==P)res=max(res,x.val);
}
return;
}
```
然后卡卡常就过去了
by Sheez @ 2023-05-15 09:54:54