bzoj 2599 [IOI2011]Race 点分

[IOI2011]Race

Time Limit: 70 Sec Memory Limit: 128 MB
Submit: 4768 Solved: 1393
[Submit][Status][Discuss]

Description

给一棵树,每条边有权.求一条简单路径,权值和等于K,且边的数量最小.N <= 200000, K <= 1000000

Input

第一行两个整数 n, k
第二..n行每行三个整数表示一条无向边的两端和权值 (注意点的编号从0开始)

Output

一个整数表示最小边数量如果不存在这样的路径输出-1

Sample Input

4 3
0 1 1
1 2 2
1 3 4

Sample Output

HINT

2018.1.3新加数据一组，未重测

点分治模板题

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 #include<iostream>

 #include<cmath>

 #include<queue>

 #include<map>

 #define ll long long

 #define inf 1000000007

 #define N 200007

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}

     while(isdigit(ch)){x=(x<<)+(x<<)+ch-'';ch=getchar();}

     return x*f;

 }

 int num=;

 int n,k;

 int total,id,f[N],siz[N];

 ll tot,a[N];

 int bs[N];

 int ans=inf;

 bool vis[N];

 int cnt,hed[N],rea[N<<],nxt[N<<],val[N<<];

 map<ll,int>p;

 void add(int u,int v,int z)

 {

     nxt[++cnt]=hed[u];

     hed[u]=cnt;

     rea[cnt]=v;

     val[cnt]=z;

 }

 void add_two_way(int x,int y,int z)

 {

     add(x,y,z);

     add(y,x,z);

 }

 void get_heart(int u,int fa)

 {

     siz[u]=,f[u]=;

     for (int i=hed[u];i!=-;i=nxt[i])

     {

         int v=rea[i];

         if (v==fa||vis[v]) continue;

         get_heart(v,u);

         siz[u]+=siz[v],f[u]=max(f[u],siz[v]);

     }

     f[u]=max(f[u],total-siz[u]);

     if (f[u]<f[id]) id=u;

 }

 void dfs(int u,int fa)

 {

     int now=tot;

     if (a[tot]==k) ans=min(ans,bs[tot]);

     if (p[k-a[tot]]) ans=min(ans,p[k-a[tot]]+bs[tot]);

     for (int i=hed[u];i!=-;i=nxt[i])

     {

         int v=rea[i],fee=val[i];

         if (fa==v||vis[v]) continue;

         bs[++tot]=bs[now]+,a[tot]=a[now]+fee;

         dfs(v,u);

     }

 }

 void calc(int u)

 {

     map<ll,int>z;

     swap(p,z),bs[u]=;

     for (int i=hed[u];i!=-;i=nxt[i])

     {

         int v=rea[i],fee=val[i];

         if (vis[v]) continue;

         bs[++tot]=,a[tot]=fee;

         dfs(v,u);

         for (int i=;i<=tot;i++)

             if (!p[a[i]]) p[a[i]]=bs[i];

             else p[a[i]]=min(p[a[i]],bs[i]);

         tot=;

     }

 }

 void solve(int u)

 {

     vis[u]=true;calc(u);int sum=total;

     for (int i=hed[u];i!=-;i=nxt[i])

     {

         int v=rea[i];

         if (vis[v]) continue;

         total=(siz[v]>siz[u])?sum-siz[u]:siz[v];

         id=,get_heart(v,u);

         solve(id);

     }

 }

 int main()

 {

     freopen("fzy.in","r",stdin);

 //    freopen("fzy.out","w",stdout);

     memset(hed,-,sizeof(hed));

     n=read(),k=read();

     for (int i=;i<n;i++)

     {

         int x=read(),y=read(),z=read();x++,y++;

         add_two_way(x,y,z);

     }

     total=f[]=n;

     get_heart(,);

     solve(id);

     if (ans==inf) puts("-1");

     else printf("%d\n",ans);

 }

秒客网