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

2

Solution

开一个100W的数组t，t[i]表示到当前处理的树的根距离为i的最小边数

对于点x，我们要统计经过x的路径的话

就分别统计x的每颗子树，在统计一颗子树的时候用t[i]更新答案

并在每统计完一颗子树后更新t数组

↑这样是为了防止统计答案的时候两个点在同一子树里

Code

1 #include
     
        2 #include
      
         3 #include
       
          4 #define N (200000+100)  5 using namespace std;  6 struct node  7 {  8     int to,next,len;  9 }edge[N*2]; 10 int n,k,sum,root,ans,INF; 11 int head[N],num_edge; 12 int depth[N],d[N],size[N],maxn[N]; 13 int dis[N],t[N*5]; 14 bool vis[N]; 15  16 void add(int u,int v,int l) 17 { 18     edge[++num_edge].to=v; 19     edge[num_edge].len=l; 20     edge[num_edge].next=head[u]; 21     head[u]=num_edge; 22 } 23  24 void Get_root(int x,int fa) 25 { 26     size[x]=1; maxn[x]=0; 27     for (int i=head[x];i!=0;i=edge[i].next) 28         if (edge[i].to!=fa && !vis[edge[i].to]) 29         { 30             Get_root(edge[i].to,x); 31             size[x]+=size[edge[i].to]; 32             maxn[x]=max(maxn[x],size[edge[i].to]); 33         } 34     maxn[x]=max(maxn[x],sum-size[x]); 35     if (maxn[x]