题目传送门
是不是我用vector的原因？
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
vector<pair<int,int> > c[N],d;
int n,m,dfn;
int dfs[N],st[N][25],dis[N],fa[N],pc[N],cnt[N],lg[N];
int read(){
char c=getchar_unlocked();
int f=1;
while(!isdigit(c)){
if(c=='-') f=-1;
c=getchar_unlocked();
}
int k=0;
while(isdigit(c)){
k=(k<<3)+(k<<1)+(c^'0');
c=getchar_unlocked();
}
return f*k;
}
void dfs1(int x,int father,int w){
fa[x]=father;
dis[x]=dis[father]+w;
dfs[x]=++dfn;
st[dfn][0]=father;
for(auto it:c[x]){
if(it.first!=father)
dfs1(it.first,x,it.second);
}
}
int mymin(int x,int y){
if(dfs[x]<dfs[y]) return x;
return y;
}
int lca(int x,int y){
if(x==y) return x;
x=dfs[x],y=dfs[y];
if(x>y)
swap(x,y);
int l=lg[y-x];
return mymin(st[x+1][l],st[y-(1<<l)+1][l]);
}
int dfs2(int x,int father){
if(c[x].size()==0)
return cnt[x]=pc[x];
int num=pc[x];
for(auto it:c[x]){
if(it.first!=father)
num+=dfs2(it.first,x);
}
return cnt[x]=num;
}
bool check(int k){
memset(pc,0,sizeof(pc));
int num=0,Max=0;
for(auto [u,v]:d){
int dij=dis[u]+dis[v]-dis[lca(u,v)]*2;
if(dij>k){
num++;
Max=max(Max,dij-k);
pc[u]++;
pc[v]++;
pc[lca(u,v)]-=2;
}
}
if(num==0) return true;
dfs2(1,0);
for(int i=1;i<=n;i++){
if(cnt[i]==num&&dis[i]-dis[fa[i]]>=Max)
return true;
}
return false;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
n=read(),m=read();
for(int i=1;i<n;i++){
int u,v,w;
u=read(),v=read(),w=read();
c[u].push_back({v,w});
c[v].push_back({u,w});
}
for(int i=1;i<=m;i++){
int u,v;
u=read(),v=read();
d.push_back({u,v});
}
dfs1(1,0,0);
for(int i=2;i<=n;i++)
lg[i]=lg[i/2]+1;
for(int j=1;j<=lg[n];j++){
for(int i=1;i<=n-(1<<j)+1;i++)
st[i][j]=mymin(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
int l=0,r=1e10;
while(l<r){
int mid=(l+r)/2;
if(check(mid))
r=mid;
else
l=mid+1;
}
cout<<l;
return 0;
}
#13 不知道为什么跑这么慢
