运输计划（倍增95pts）
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 300005
int n,m,cnt,maxi,ans,cha[MAXN],tot[MAXN],beyond,longest,
head[MAXN],fa[MAXN][25],dep[MAXN],dis[MAXN],tofa[MAXN];
struct edge{
int v,w,next;
}e[MAXN<<1];
inline void add(int u,int v,int w){
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt;
}
struct node{
int u,v,lca,dis;
}s[MAXN];
inline bool cmp(node x,node y){
return x.dis>y.dis;
}
inline void deal_first(int u,int fau){
// printf("%d %d\n",u,fau);
dep[u]=dep[fau]+1;
fa[u][0]=fau;
for(int i=1;(1<<i)<=dep[u];i++)fa[u][i]=fa[fa[u][i-1]][i-1];
for(int i=head[u];i!=-1;i=e[i].next){
if(e[i].v==fau)continue;
tofa[e[i].v]=e[i].w;
dis[e[i].v]=dis[u]+e[i].w;
deal_first(e[i].v,u);
}
}
inline int lca(int x,int y){
if(dep[x]<dep[y])std::swap(x,y);
for(int i=20;i>=0;i--)
if(dep[x]-dep[y]>=(1<<i))x=fa[x][i];
if(x==y)return x;
for(int i=20;i>=0;i--){
if(fa[x][i]!=fa[y][i]){
x=fa[x][i];
y=fa[y][i];
}
}
return fa[x][0];
}
inline int getdfs(int u){
tot[u]=cha[u];
for(int i=head[u];i!=-1;i=e[i].next){
int v=e[i].v;
if(v==fa[u][0])continue;
tot[u]+=getdfs(v);
}
if(tot[u]==beyond)longest=std::max(longest,tofa[u]);
return tot[u];
}
inline bool check(int x){
beyond=longest=0;
memset(cha,0,sizeof(cha));
memset(tot,0,sizeof(tot));
for(int i=1;i<=m;i++){
if(s[i].dis<=x)break;
beyond++;
cha[s[i].u]++;
cha[s[i].v]++;
cha[s[i].lca]-=2;
}
getdfs(1);
if(s[1].dis-longest<=x)return true;
return false;
}
int main(){
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m);
for(int i=1;i<=n-1;i++){
int a,b,t;
scanf("%d%d%d",&a,&b,&t);
add(a,b,t);
add(b,a,t);
}
// printf("alive\n");
deal_first(1,0);
// printf("alive\n");
for(int i=1;i<=m;i++){
scanf("%d%d",&s[i].u,&s[i].v);
s[i].lca=lca(s[i].u,s[i].v);
s[i].dis=dis[s[i].u]+dis[s[i].v]-2*dis[s[i].lca];
maxi=std::max(maxi,s[i].dis);
}
// printf("alive\n");
std::sort(s+1,s+m+1,cmp);
int l=0,r=maxi;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid))ans=mid,r=mid-1;
else l=mid+1;
}
// printf("alive\n");
printf("%d\n",ans);
}又出现这个错误：head没memset见祖宗
优质内容筛选与推荐>>1、Wordpress<=4.6.1使用语言文件任意代码执行漏洞分析
2、数据库SQL性能优化（三）
3、告知服务器意图的HTTP方法1GET:获取资源2POST：传输实体主体3PUT:传输文件4HEAD:获得报文首部5DELETE:删除文件6OPTIONS：询问支持的方法一般网站只用G
4、码农晋升为技术管理者后，痛并快乐着的纠结内心
5、专栏|有趣！用计算机视觉技术与PaddlePaddle打造AI控烟项目