社区讨论
为什么ce
P1084[NOIP 2012 提高组] 疫情控制参与者 3已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @mi6hjhpn
- 此快照首次捕获于
- 2025/11/20 04:59 4 个月前
- 此快照最后确认于
- 2025/11/20 04:59 4 个月前
CPP
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fod(i,a,b) for(i=a;i>=b;i--)
typedef long long ll;
const int maxn=100007;
using namespace std;
ll i,j,k,l,t,n,m,ans,r,mid,yi,er;
ll a[maxn];
ll first[maxn*2],next[maxn*2],last[maxn*2],chang[maxn*2],num;
ll b[maxn],tot,f[maxn][18],g[maxn][18],deep[maxn];
ll c[maxn],d[maxn],e[maxn],wwa,vv;
bool bz[maxn],az[maxn];
struct node{
ll w,v;
}w[maxn];
struct nod{
ll a,b;
}v[maxn];
void add(ll x,ll y,ll z){
last[++num]=y;
next[num]=first[x];
first[x]=num;
chang[num]=z;
}
void dfs(ll x,ll y){
int i,j,k;
for(i=first[x];i;i=next[i]){
if(last[i]!=y){
f[last[i]][0]=x;
g[last[i]][0]=chang[i];
dfs(last[i],x);
}
}
}
void suan(ll x,ll y){
int i,j,k=0;
if(k+g[x][0]<=y&&f[x][0]){
x=f[x][0];
k+=g[x][0];
}
yi=x;er=k;
}
bool cmp(nod x,nod y){
return x.a<y.a;
}
bool cmp1(node x,node y){
return x.w<y.w;
}
void dfs1(ll x){
bool dz=1,ez=1;
for(int i=first[x];i;i=next[i]){
if(last[i]!=f[x][0]){
dfs1(last[i]);
dz=0;
if(bz[last[i]]==0)ez=0;
}
}
if(ez&&x!=1&&dz==0)bz[x]=1;
}
bool pan(ll x){
ll i,j,p,q,o;
wwa=vv=0;
memset(bz,0,sizeof(bz));
fo(i,1,m){
o=0;
q=a[i];p=0;
fod(j,17,0){
if(p+g[q][j]<=x&&f[q][j]){
p+=g[q][j];
q=f[q][j];
}
}
if(q!=1){
bz[q]=1;
}
else{
w[++wwa].w=x-p;
q=a[i];
fod(j,17,0)if(f[q][j]>1)q=f[q][j];
w[wwa].v=q;
}
}
dfs1(1);
sort(w+1,w+1+wwa,cmp1);
for(i=first[1];i;i=next[i]){
if(!bz[last[i]]){
v[++vv].a=chang[i];
v[vv].b=last[i];
}
}
sort(v+1,v+1+vv,cmp);
if(wwa<vv)return 0;
v[vv+1].a=0x7fffffff;
k=1;
fo(i,1,wwa){
if(!bz[w[i].v])bz[w[i].v]=1;
else if(w[i].w>=v[k].a){
bz[v[k].b]=1;
k++;
}
while(bz[v[k].b])k++;
}
if(k>vv)return 1;
else return 0;
}
int main(){
scanf("%lld",&n);
fo(i,1,n-1){
scanf("%lld%lld%lld",&k,&l,&t);
add(k,l,t);
add(l,k,t);
}
dfs(1,0);
fo(j,1,17){
fo(i,1,n){
f[i][j]=f[f[i][j-1]][j-1];
g[i][j]=g[f[i][j-1]][j-1]+g[i][j-1];
}
}
scanf("%lld",&m);
fo(i,1,m){
scanf("%lld",&a[i]);
}
l=0;r=1000000000;
while(l<r){
mid=(l+r)/2;
if(pan(mid))r=mid;else l=mid+1;
}
printf("%lld\n",l);
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...