bzoj2599: [IOI2011]Race

链接&&题面

https://www.lydsy.com/JudgeOnline/problem.php?id=2599

思路

没啥思路，就是模板题
只不过顺便维护桶的时候维护一个最小边数
不过最气人的是
我用手写栈会RE，会WR，会运行错误
我用stl的queue会wrong，会TLE
我用stl的stack才AC
╮(╯▽╰)╭调了我一天半
只得说mmp
update
luogu上开o2就wrong，不开就A

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=6e5+7;
int read() {
    int x=0,f=1;char s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
int n,k,rt,rt_val,tot,ans=0x3f3f3f3f;
int T[10000007],vis[N];
int siz[N],stak[N],dep[N],T_dep[N],q[N*10];
ll dis[N];
struct node {
    int u,v,nxt;
    ll q;
}e[N<<1];
int head[N<<1],cnt;
void add(int u,int v,int q) {
    e[++cnt].v=v;
    e[cnt].q=q;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
void getrt(int u,int f) {
    siz[u]=1;
    int tmp=0;
    for(int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if(v==f||vis[v]) continue;
        getrt(v,u);
        siz[u]+=siz[v];
        tmp=max(tmp,siz[v]);
    }
    tmp=max(tmp,tot-siz[u]);
    if(tmp<rt_val) rt_val=tmp,rt=u;
}
void getdis(int u,int f) {
    stak[++stak[0]]=u;
    for(int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if(v==f||vis[v]) continue;
        dis[v]=dis[u]+e[i].q;
        dep[v]=dep[u]+1;
        getdis(v,u);
    }
}
// queue<int> q;
stack<int> Q;
void calc(int u) {
    T[0]=1;T_dep[0]=0;
    // q[0]=0;
    // Q.clear();
    for(int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if(vis[v]) continue;
        stak[0]=0,dis[v]=e[i].q,dep[v]=1;
        getdis(v,u);
        for(int j=1;j<=stak[0];++j) {
            if(k-dis[stak[j]]>=0&&T[k-dis[stak[j]]]) {
                ans=min(ans,dep[stak[j]]+T_dep[k-dis[stak[j]]]);
            }
        }
        for(int j=1;j<=stak[0];++j) {
            if(dis[stak[j]]>k) continue;
            Q.push(dis[stak[j]]);
            // q[++q[0]]=dis[stak[j]];
            // q.push(dis[stak[j]]);
            // cout<<++q[0]<<"\n";
            T[dis[stak[j]]]=1;
            if(T_dep[dis[stak[j]]]==0) T_dep[dis[stak[j]]]=0x3f3f3f3f;
            T_dep[dis[stak[j]]]=min(T_dep[dis[stak[j]]],dep[stak[j]]);
        }
    }
    // T_dep[0]=0x3f3f3f3f;
    while(!Q.empty()) {
        T[Q.top()]=0;
        T_dep[Q.top()]=0x3f3f3f3f;
        Q.pop();
    }
    // memset(T,0,sizeof(T));
    // memset(T_dep,0x3f,sizeof(T_dep));
    // for(int i=1;i<=q[0];++i) T[q[i]]=0,T_dep[q[i]]=0x3f3f3f3f;
}
void dfs(int u) {
    vis[u]=1;
    calc(u);
    for(int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if(vis[v]) continue;
        tot=siz[v],rt_val=0x3f3f3f3f,rt=0;
        getrt(v,0);
        dfs(rt);
    }
}
int main() {
    // freopen("a.in","r",stdin);
    // freopen("a.out","w",stdout);
    memset(T_dep,0x3f,sizeof(T_dep));
    n=read(),k=read();
    for(int i=1;i<n;++i) {
        int x=read()+1,y=read()+1,z=read();
        add(x,y,z);
        add(y,x,z);
    }
    rt_val=tot=n;
    getrt(1,0);
    dfs(rt);
    if(ans==0x3f3f3f3f) ans=-1;
    printf("%d\n",ans);
    return 0;
}