为什么我的只有55
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=3000003;
int n,m;
int fa[maxn][30],deep[maxn],pre[maxn],tmp[maxn],len[maxn];
struct node{
int to;
int v;
};
vector<node> e[maxn];
bool used[maxn];
void dfs(int x){
used[x]=true;
for(int i=0;i<e[x].size();i++){
int &t=e[x][i].to;
if(!used[t]){
fa[t][0]=x;
deep[t]=deep[x]+1;
len[t]=len[x]+e[x][i].v;
pre[t]=e[x][i].v;
dfs(t);
}
}
}
void init(){
for(int j=1;j<=29;j++){
for(int i=1;i<=n;i++){
fa[i][j]=fa[fa[i][j-1]][j-1];
}
}
}
int Lca(int a,int b){
if(deep[a]<deep[b])
swap(a,b);
int dc=deep[a]-deep[b];
for(int i=0;i<=29;i++){
if(1<<i&dc){
a=fa[a][i];
}
}
if(a==b){
return a;
}
for(int i=29;i>=0;i--){
if(fa[a][i]!=fa[b][i])
a=fa[a][i],b=fa[b][i];
}
return fa[a][0];
}
struct point{
int s;
int t;
int dist;
int lca;
}qu[maxn];
int L,R;
int a,b,c;
int ans=1e9;
int cnt=0;
int distt=0;
bool check(int x){
memset(tmp,0,sizeof(tmp));
cnt=0;distt=0;
//int ac=0;
for(int i=1;i<=m;i++){
if(qu[i].dist>x){
a=qu[i].s;b=qu[i].t;c=qu[i].lca;
tmp[a]++;tmp[b]++,tmp[qu[i].lca]-=2;
distt=max(distt,qu[i].dist-x);
cnt++;
}
}
if(!cnt)return true;
for(int i=n;i>=1;i--){
tmp[fa[i][0]]+=tmp[i];
}
for(int i=1;i<=n;i++){
if(tmp[i]==cnt&&pre[i]>=distt){
return true;
}
}
return false;
}
int main(){
cin>>n>>m;
node p,q;
for(int i=1;i<n;i++){
cin>>a>>b>>c;
p.to=b;p.v=c;
q.to=a;q.v=c;
e[a].push_back(p);
e[b].push_back(q);
}
fa[1][0]=0;
deep[1]=0;
dfs(1);
init();
int u,v;
for(int i=1;i<=m;i++){
cin>>u>>v;
qu[i].s=u;
qu[i].t=v;
qu[i].lca=Lca(u,v);
qu[i].dist=len[u]+len[v]-len[qu[i].lca]*2;
R=max(R,qu[i].dist);
}
while(L<=R){
int mid=L+(R-L)/2;
if(check(mid)){
ans=min(ans,mid);
R=mid-1;
}
else{
L=mid+1;
}
}
cout<<ans;
return 0;
}
```
by 长颈鹿 @ 2017-11-05 10:54:09
用链式前向星写临接表试试
by EndA @ 2017-11-07 17:55:13