哪位大佬帮忙看看我这个哪里错了

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define inf 300000000
int m,n,fa[300001][20],dis[300001][20],dep[300001],
s[300001],t[300001],lca[300001],len[300001],
ans,
cnt=1,ce[300001],
k;
int res[300001],maxlen,num;
struct edge{
int t,d,next;
}e[300001];
int max(int x,int y){
return x>y?x:y;
}
void add(int u,int v,int d){
e[cnt].t=v;
e[cnt].d=d;
e[cnt].next = ce[u];
ce[u]=cnt++;
}
void budtree(int v){
int p=ce[v];
while (p){
if(e[p].t==fa[v][0]) p=e[p].next ;
if(!p)break;
fa[e[p].t][0]=v;
dis[e[p].t][0]=e[p].d;
dep[e[p].t]=dep[v]+1;

budtree(e[p].t);
p=e[p].next;
}
}
int getlca(int u,int v){
int t,i;
if(dep[u]<dep[v]) t=u,u=v,v=t;
int p;
if(dep[u]>dep[v]){
p=dep[u]-dep[v];
t=0;
while(p){
if(p&1){
u=fa[u][t];
}
t++;p>>=1;
}
}
p=(int)log2(dep[u])+1;
for(i=p;i>=0;i--){
if(fa[u][i]!=fa[v][i]){
u=fa[u][i];v=fa[v][i];
}
}
return fa[u][0];
}
int getlong(int u,int v){
if(u==v) return 0;
int t;
if(dep[u]<dep[v]) t=u,u=v,v=t;
int l=0,p,i=0;
p=dep[u]-dep[v];
while(p){
if(p&1){
l+=dis[u][i];
}
i++;
p>>=1;
}
return l;
}
void sort(int le,int ri){
if(le==ri) return;
int val,i,j,a,b,c;
i=le;
j=ri;
val=len[le];
a=s[le];b=t[le];c=lca[le];
while(i<j){
while(i<j && len[j]>=val) j--;
if(i<j) len[i]=len[j],s[i]=s[j],t[i]=t[j],lca[i]=lca[j],i++;
while(i<j && len[i]<=val) i++;
if(i<j) len[j]=len[i],s[j]=s[i],t[j]=t[i],lca[j]=lca[i],j--;
}
len[i]=val;
s[i]=a;t[i]=b;lca[i]=c;
if(i>le) sort(le,i-1);
if(i<ri) sort(i+1,ri);
return;
}
int getline(int v){
int p=ce[v],sum=0;
while(p){
if(e[p].t==fa[v][0]) p=e[p].next ;
if(!p)break;
sum+=getline(e[p].t);
p=e[p].next;
}
sum+=res[v];
if(sum==num) maxlen=max(dis[v][0],maxlen);
return sum;
}
int check(int mid){
int i;
num=0;
for (i=m;i>=1;i--){
if(len[i]>mid) num++;
else break;
}
if(!num) return 1;
memset(res,0,sizeof(res));
maxlen=0;
for(i=m;i>m-num;i--){
res[s[i]]+=1;
res[t[i]]+=1;
res[lca[i]]-=2;
}
getline(1);
if(len[m]-maxlen<=mid) return 1;
else return 0;
}
int main(){
//FILE *fin,*fout;
//fin=fopen("main.in","r");
//fout=fopen("main.out","w");
memset(ce,0,sizeof(ce));
memset(e,0,sizeof(e));
scanf("%d %d",&n,&m);
int i,j,a,b,c;
for (i=1;i<n;i++){
scanf("%d %d %d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
for(i=1;i<=m;i++){
scanf("%d %d",&s[i],&t[i]);
}
dep[1]=1;
fa[1][0]=1;
dis[1][0]=0;
budtree(1);
k=(int)log2(n)+1;
for(i=1;i<=n;i++){
for(j=1;j<=k;j++){
fa[i][j]=fa[fa[i][j-1]][j-1];
dis[i][j]=dis[i][j-1]+dis[fa[i][j-1]][j-1];
}
}
for(i=1;i<=m;i++){
lca[i]=getlca(s[i],t[i]);
len[i]=getlong(s[i],lca[i])+getlong(t[i],lca[i]);
}
sort(1,m);
int le=0,ri=1000*n,mid;
while(le<ri){
mid=(le+ri)>>1;
a=check(mid);
if(a){
ans=mid;
ri=mid;
}else le=mid+1;
}
printf("%d",ans);
return 0;
}

1 条评论

  • 1

信息

ID
1983
难度
8
分类
(无)
标签
递交数
2350
已通过
314
通过率
13%
上传者