悬赏 5 元求调
查看原帖
悬赏 5 元求调
246331
mystic_qwq楼主2024/6/8 18:14

求大佬调一下这个程序QwQ 支持微信付款

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=5e4+1,M=N,Lg=log2(N)+1;
int n,m;
vector<int> P[N];
vector<pair<int,int>> G[N];
void add(int u,int v,int w){
  G[u].pb({v,w}),G[v].pb({u,w});
  P[u].pb(v),P[v].pb(u);
}
struct Camp{
  int id,w;
  bool operator<(Camp&a)const{
    return w>a.w?1:0;
  }
};
vector<Camp> camp;
using ll=long long;
struct Bin{
  ll t; int p,b; // time, pos, belong to which subtree rooted as 1's son
  bool operator<(Bin&a)const{
    return t<a.t?1:0;
  }
}bin[M],org[M];
bool mark[N];
bool chktree(int u,int fa){
  if(mark[u]) return 1;
  for(int v:P[u])
    if(v!=fa&&!chktree(v,u)) return 0;
  return 1;
}
int f[N][Lg]; ll g[N][Lg];
void dfs0(int u,int fa){
  for(auto[v,w]:G[u])if(v!=fa)
    f[v][0]=u,g[v][0]=w,dfs0(v,u);
  for(int i=1;i<=log(n);++i){  
    f[u][i]=f[f[u][i-1]][i-1],
    g[u][i]=g[u][i-1]+g[f[u][i-1]][i-1];
  }
}
int Bel[N];
void Mark(int x,int u,int fa){
  Bel[u]=x;
  for(int v:P[u]) if(v!=fa) Mark(x,v,u);
}
ll l=0,r=1e18,lim;
void getpos(Bin&bbin){
  auto&[t,p,b]=bbin;
  for(int i=log2(n);~i;--i){
    if(g[p][i]<=lim-t) 
      t+=g[p][i],p=f[p][i];
  }
  if(!p) p=1;
}
bool used[N];
bool check(){
  camp.clear();
  memset(mark+1,0,n<<2);
  memset(used+1,0,m);
  for(int i=1;i<=m;++i){ 
    getpos(bin[i]=org[i]);
    if(bin[i].p!=1) mark[bin[i].p]=1;
  }
  for(auto[v,w]:G[1]) if(!chktree(v,1)) camp.pb({v,w});
  sort(bin+1,bin+m+1),sort(camp.begin(),camp.end());
  for(auto[v,w]:camp) 
  for(int i=1;i<=m;++i){ 
    if(!used[i]){ 
      auto[t,p,b]=bin[i];
      if((lim-t<w&&b==v)||lim-t>=w) {used[i]=1;goto _;}
    }
    return 0;_:;
  }
  return 1;
}
main(){
  cin>>n;
  for(int u,v,w,i=1;i<n;++i)
    cin>>u>>v>>w,add(u,v,w);
  for(int v:P[1]) Mark(v,v,1); dfs0(1,0);
  cin>>m;
  for(int i=1;i<=m;++i)
    cin>>org[i].p,org[i].b=Bel[org[i].p];
  while(l<=r) lim=l+r>>1,check()?r=lim-1:(l=lim+1);
  if(r==1e18) cout<<"-1\n"; else cout<<r+1<<'\n';
}
2024/6/8 18:14
加载中...