P4149 [IOI2011]Race

akxlaizh · 2021-09-26 18:51:55 · 个人记录

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map> 
#include <vector> 
#include <queue>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,int>  PLI;
const int N = 2e5+5,mod=1e9+7;

void add(int &a,LL b){a=(a+b)%mod;return ;}
int h[N],ne[N<<1],e[N<<1],w[N<<1],idx;
void add(int h[],int a,int b,int c){w[idx]=c;e[idx]=b;ne[idx]=h[a];h[a]=idx++;return ;}
map<LL,int>ma;
int son[N],ans=0x3f3f3f3f,Y,n,k;
int dfn[N],id[N],siz[N],deepth[N];
LL X,we[N];

inline void dfs(int u,int fa)
{
    siz[u]=1;
    id[u]=idx;
    dfn[idx++]=u;
    for(int i=h[u];~i;i=ne[i])
    {
        if(e[i]==fa)continue;
        we[e[i]]=we[u]+w[i];
        deepth[e[i]]=deepth[u]+1;
        dfs(e[i],u);
        if(siz[son[u]]<siz[e[i]])son[u]=e[i];
        siz[u]+=siz[e[i]];
    }
}

void calc(int u,int val)
{
    for(int i=id[u];i<=id[u]+siz[u]-1;i++)//不看dfn序就爆栈了。哎。 
    {
        int t=dfn[i],d=we[t],deep=deepth[t];
        if(val==1){
            if(ma.find(X-d)!=ma.end())ans=min(ans,ma[X-d]+deep-Y);
        }
        else {
            if(ma.find(d)!=ma.end())ma[d]=min(ma[d],deep);
            else ma[d]=deep;
        }
    }
}

void dfs(int u,int fa,int keep)
{
    for(int i=h[u];~i;i=ne[i])
    {
        int t=e[i];
        if(t==son[u]||t==fa)continue;
        dfs(t,u,0);
    }
    if(son[u])dfs(son[u],u,1);
    X=2*we[u]+k,Y=deepth[u]*2;
    for(int i=h[u];~i;i=ne[i])// 子树更新答案和删除答案； 
    {
        int t=e[i];
        if(t==son[u]||t==fa)continue;
        calc(t,1);
        calc(t,0);
    }
    //因为不能直接删除和加入这棵树而是加入或删除她的一系列子树 所以要判断根节点； 
    if(ma.find(we[u])!=ma.end())ma[we[u]]=min(ma[we[u]],deepth[u]);
    else ma[we[u]]=deepth[u];

    if(ma.find(we[u]+k)!=ma.end())ans=min(ans,ma[we[u]+k]+deepth[u]-Y);
    X=0,Y=0;
    if(!keep)ma.clear();// 。。。 
}

int main()
{
//  freopen("D:\\in.txt","r",stdin);
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)h[i]=-1; 

    for(int i=1;i<n;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(h,u+1,v+1,w);
        add(h,v+1,u+1,w);
    }
    idx=0;
    dfs(1,0);
    dfs(1,0,1);
    if(ans==0x3f3f3f3f)puts("-1");
    else cout<<ans<<endl;
    return 0;
}