本人一开始是20pts,代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i,a,b) for(int i=a;i<=b;i++)
const int N=3e5+10;
int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}
while('0'<=c&&c<='9')x=x*10+c-'0',c=getchar();
return x*f;
}
struct Edge{int u,v,w;}G[2*N];
struct Task{int u,v,len;}task[N];
int n,m,d[N],dis[N],head[N],nxt[2*N],idx;
int top[N],dep[N],siz[N],hson[N],fa[N];
void add_edge(int u,int v,int w){
G[++idx]={u,v,w},nxt[idx]=head[u],head[u]=idx;
}
void dfs1(int u,int f){
fa[u]=f,siz[u]=1,dep[u]=dep[f]+1;
for(int j=head[u];j;j=nxt[j]){
int v=G[j].v,w=G[j].w;
if(v==f)continue;
dis[v]=dis[u]+w;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[hson[u]])hson[u]=v;
}
}
void dfs2(int u,int t){
top[u]=t;
if(!hson[u])return;
dfs2(hson[u],t);
for(int j=head[u];j;j=nxt[j]){
int v=G[j].v;
if(v!=fa[u]&&v!=hson[u])dfs2(v,v);
}
}
int lca(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]>dep[top[v]])u=fa[top[u]];
else v=fa[top[v]];
}
return dep[u]>dep[v]?v:u;
}
int dfs(int u){
for(int j=head[u];j;j=nxt[j]){
int v=G[j].v;
if(v==fa[u])continue;
d[u]+=dfs(v);
}
return d[u];
}
int check(int mid){
memset(d,0,sizeof(d));
int cnt=0,maxt=0;
FOR(i,1,m){
int u=task[i].u,v=task[i].v,l=task[i].len;
if(l>mid){
cnt++;
maxt=max(maxt,l);
d[u]++,d[v]++,d[lca(u,v)]-=2;
}
}
dfs(1);
FOR(i,1,idx){
int u=G[i].u,v=G[i].v,w=G[i].w;
if((d[u]==cnt||d[v]==cnt)&&maxt-w<=mid)return 1;
}
return 0;
}
signed main(){
n=read(),m=read();
FOR(i,1,n-1){
int u=read(),v=read(),w=read();
add_edge(u,v,w),add_edge(v,u,w);
}
FOR(i,1,m){
int u=read(),v=read();
task[i]={u,v,0};
}
dfs1(1,0),dfs2(1,1);
FOR(i,1,m){
int u=task[i].u,v=task[i].v;
task[i].len=dis[u]+dis[v]-2*dis[lca(u,v)];
}
int l=0,r=1001,ans=0;
while(l<r){
int mid=(l+r)>>1;
if(check(mid))ans=mid,r=mid;
else l=mid+1;
}
printf("%lld",ans);
return 0;
}
经过找虫,发现锅出在二分上界 r 只有1001,应该是 1001*N。
然后又交了一发,65pts,代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i,a,b) for(int i=a;i<=b;i++)
const int N=3e5+10;
int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}
while('0'<=c&&c<='9')x=x*10+c-'0',c=getchar();
return x*f;
}
struct Edge{int u,v,w;}G[2*N];
struct Task{int u,v,len;}task[N];
int cmp(Task t1,Task t2){
return t1.len>t2.len;
}
int n,m,d[N],dis[N],head[N],nxt[2*N],idx;
int top[N],dep[N],siz[N],hson[N],fa[N];
void add_edge(int u,int v,int w){
G[++idx]={u,v,w},nxt[idx]=head[u],head[u]=idx;
}
void dfs1(int u,int f){
fa[u]=f,siz[u]=1,dep[u]=dep[f]+1;
for(int j=head[u];j;j=nxt[j]){
int v=G[j].v,w=G[j].w;
if(v==f)continue;
dis[v]=dis[u]+w;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[hson[u]])hson[u]=v;
}
}
void dfs2(int u,int t){
top[u]=t;
if(!hson[u])return;
dfs2(hson[u],t);
for(int j=head[u];j;j=nxt[j]){
int v=G[j].v;
if(v!=fa[u]&&v!=hson[u])dfs2(v,v);
}
}
int lca(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]>dep[top[v]])u=fa[top[u]];
else v=fa[top[v]];
}
return dep[u]>dep[v]?v:u;
}
int dfs(int u){
for(int j=head[u];j;j=nxt[j]){
int v=G[j].v;
if(v==fa[u])continue;
d[u]+=dfs(v);
}
return d[u];
}
int check(int mid){
memset(d,0,sizeof(d));
int cnt=0,maxt=0;
FOR(i,1,m){
int u=task[i].u,v=task[i].v,len=task[i].len;
if(len<=mid)break;
cnt++;
maxt=max(maxt,len);
d[u]++,d[v]++,d[lca(u,v)]-=2;
}
dfs(1);
FOR(i,1,idx){
int u=G[i].u,v=G[i].v,w=G[i].w;
if((d[u]==cnt||d[v]==cnt)&&maxt-w<=mid)return 1;
}
return 0;
}
signed main(){
n=read(),m=read();
FOR(i,1,n-1){
int u=read(),v=read(),w=read();
add_edge(u,v,w),add_edge(v,u,w);
}
FOR(i,1,m){
int u=read(),v=read();
task[i]={u,v,0};
}
dfs1(1,0),dfs2(1,1);
FOR(i,1,m){
int u=task[i].u,v=task[i].v;
task[i].len=dis[u]+dis[v]-2*dis[lca(u,v)];
}
sort(task+1,task+m+1,cmp);
int l=0,r=1001*N,ans=0;
while(l<r){
int mid=(l+r)>>1;
if(check(mid))ans=mid,r=mid;
else l=mid+1;
}
printf("%lld",ans);
return 0;
}
又经过漫长的找虫,发现是check写挂了,具体来说 :
if((d[u]==cnt||d[v]==cnt)&&maxt-w<=mid)return 1;
这里应该是 u 和 v 中深度大的那个点的 d=cnt 才能判断被经过 cnt 次,希望大家不要和我犯一样的错误。