仍然是大规模解决树上路径的问题。
显然是点分治，但是因为我太菜了想不到应该怎么点分治，还是借鉴dalao的经验才想出来。
我们用tmp[i]表示在当前子树中，经过长度为i的路径最少需要几条边。那么转移的方程就是tmp[m] = tmp[m-dis[i]] + d[i],其中m是要求的路径长度。
不过这题并不是这么简单就完事了的。
这次的点分治与众不同，以往我们都是直接先进去从最大的树开始dfs，不过这次不是，这次进去之后先啥也不干，先去找自己的子树，在子树中统计一遍答案之后，dfs进去更新答案，把每个节点的tmp值更新为最优的。
之后把所有子树统计完了之后，我们还得再从新进去dfs一遍，把所有的tmp值重新更新为INF，这样才能继续向下递归求解。（感觉有点难理解orz）
其实是因为这题要求的不是什么路径条数，我们一开始是统计这棵树，但是其实在每次计算的过程中，由于tmp是一个全局变量，所以我们在访问之后的子树的时候tmp值都会被用到。但是这种统计方法难以把所有情况统计全，所以我们还必须得递归下去计算。每次递归之前需要把tmp变为INF值，否则会影响子树中的更新（因为这一棵子树内的情况于外面是不影响的）
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<queue> #include<cstring> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') using namespace std; typedef long long ll; const int M = 200005; const int N = 1000005; const int INF = 1e9+7; int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >='0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } struct edge { int next,to,v; }e[M<<1]; int ecnt,head[M],maxs[M],size[M],dis[M],tmp[N],d[M]; bool vis[M]; int sum,root,ans = INF,tot,n,m,x,y,z; void add(int x,int y,int z) { e[++ecnt].v = z; e[ecnt].to = y; e[ecnt].next = head[x]; head[x] = ecnt; } void getroot(int x,int fa)//常规找重心 { size[x] = 1,maxs[x] = 0; for(int i = head[x];i;i = e[i].next) { int t = e[i].to; if(t == fa || vis[t]) continue; getroot(t,x); size[x] += size[t]; maxs[x] = max(maxs[x],size[t]); } maxs[x] = max(maxs[x],sum - size[x]); if(maxs[x] < maxs[root]) root = x; } void calc(int x,int fa) { if(dis[x] <= m) ans = min(ans,tmp[m-dis[x]] + d[x]);//更新答案 for(int i = head[x];i;i = e[i].next) { int t = e[i].to; if(t == fa || vis[t]) continue; dis[t] = dis[x] + e[i].v,d[t] = d[x] + 1;//计算路径长和边数 calc(t,x);//继续向下递归计算 } } void dfs(int x,int fa,bool flag)//在这里更新答案 { if(dis[x] <= m) tmp[dis[x]] = flag? min(tmp[dis[x]],d[x]) : INF;//后一半操作是用来还原为INF的 for(int i = head[x];i;i = e[i].next) { int t = e[i].to; if(t == fa || vis[t]) continue; dfs(t,x,flag);//继续递归还原 } } void solve(int x) { vis[x] = 1,tmp[0] = 0;//注意这里！因为自己走到自己的路径长度就是0，经过了0条边 for(int i = head[x];i;i = e[i].next) { int t = e[i].to; if(vis[t]) continue; dis[t] = e[i].v,d[t] = 1; calc(t,0),dfs(t,0,1);//先统计答案，再更新 } for(int i = head[x];i;i = e[i].next) if(!vis[e[i].to]) dfs(e[i].to,0,0); for(int i = head[x];i;i = e[i].next) { int t = e[i].to; if(vis[t]) continue; sum = size[t],maxs[root = 0] = n; getroot(t,0),solve(root);//递归求解 } } int main() { n = read(),m = read(); rep(i,1,m) tmp[i] = INF; rep(i,1,n-1) x = read()+1,y = read()+1,z = read(),add(x,y,z),add(y,x,z);//注意点是从0开始计数的 sum = maxs[root] = n; getroot(1,0); solve(root); if(ans != INF) printf("%d ",ans); else printf("-1 "); return 0; }