题目描述

给一棵树，每条边有权。求一条简单路径，权值和等于 KKK ，且边的数量最小。

输入输出格式

输入格式：

第一行：两个整数 n,kn,kn,k 。

第二至 nnn 行：每行三个整数，表示一条无向边的两端和权值 (注意点的编号从 000 开始)。

输出格式：

一个整数，表示最小边数量。

如果不存在这样的路径，输出 −1-1−1 。

输入输出样例

输入样例#1： 复制

4 3

0 1 1

1 2 2

1 3 4

输出样例#1： 复制

2

说明

n≤200000,K≤1000000n\le 200000,K\le 1000000n≤200000,K≤1000000 。

解题思路

点分治。用一个叫f的桶来维护，时间复杂度O(nlogn)

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int MAXN = 200005;const int inf = 0x3f3f3f3f;inline int rd(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f;}int n,k,ans=0x3f3f3f3f;int head[MAXN],cnt,sum,mx,rt,siz[MAXN];int to[MAXN<<1],nxt[MAXN<<1],val[MAXN<<1];int f[1000005],stk[MAXN],top;bool vis[MAXN];queue
           
             Q,q;inline void add(int bg,int ed,int w){ to[++cnt]=ed,val[cnt]=w,nxt[cnt]=head[bg],head[bg]=cnt;}inline void dfs(int x,int fa){ siz[x]=1; for(register int i=head[x];i;i=nxt[i]){ int u=to[i];if(vis[u] || u==fa) continue; dfs(u,x);siz[x]+=siz[u]; }}inline void getrt(int x,int fa){ int k=0; for(register int i=head[x];i;i=nxt[i]){ int u=to[i];if(vis[u] || u==fa) continue; getrt(u,x);k=max(k,siz[u]); } k=max(k,sum-siz[x]); if(k
            
             k) continue; if(!f[now]) f[now]=len; else f[now]=min(f[now],len); } } for(register int i=1;i<=top;i++) f[stk[i]]=0;top=0; for(register int i=head[x];i;i=nxt[i]){ int u=to[i];if(vis[u]) continue; dfs(u,x);sum=mx=siz[u];rt=0;getrt(u,x);// cout<
             <<" "<<