題意：給一棵樹,每條邊有權.求一條路徑,權值和等於K,且邊的數量最小. （我會告訴你這就是題面？）
BZOJ的題就是好啊！一句話題意，贊一個。
這道題的思路還是點分治 ，類似於前面那篇文章裡的兩題，只不過轉換成了求最小而不是計數，，，
每次找好重心u後，我們只考慮以u為根的子樹，u的子樹可以分治下去搞。
我們只考慮經過根的路徑
由前面兩題，可以很輕松的想到這樣一個方法：
先搜出當前樹所有的二元組（W,Dep），然後排序，掃描，但是注意，有可能兩個點來自於同一棵子樹，如果給二元組加一個信息屬於哪顆子樹，就變成了三元組。。。。判斷兩個元素是否滿足條件需要滿足三個信息，很是復雜啊。。不過我還是用這個方法寫了老半天，最後實在搞不定就想其他方法了。
還是由以前做過的一些樹形DP得到的啟發，我們一棵一棵子樹的去合並，也就是在當前子樹找一個點（w,dep），在前面的子樹找一個點，這個點
到根的權值和是 K-W ，並且深度最小，我們就記為dp[K-w]好了，（這種方法在合並子樹的問題上還是蠻常用的），然後我們每次先詢問再更新DP數組就好了，要注意DP數組的初始化，不能全部都清空，要不果斷TLE。。。。
這題的數據應該還是蠻好造的吧。。。。
附上代碼：速度略慢啊，跑了17s多
[cpp]
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 222222;
struct Divided_Conquer {
struct Edge{
int v , w;
Edge(){}
Edge(int v,int w): v(v),w(w) {
}
};
bool Del[maxn];
vector<Edge> E[maxn];
int N , K;
int size[maxn] , opt[maxn] ,dp[1000010];
vector<int> tnode ;
vector<pair<int,int> > now;
void Dfs(int u,int f)
{
tnode.push_back(u);
size[u] = 1;
opt[u] = 0;
for(vector<Edge>::iterator it = E[u].begin(); it != E[u].end(); it++) {
if(!Del[it->v] && it->v != f) {
Dfs(it->v,u);
size[u] += size[it->v];
opt[u] = max(opt[u],size[it->v]);
}
}
}
int Get_Root(int u)
{
tnode.clear();
Dfs(u,-1);
int mi = maxn , ans = -1;
for(vector<int>::iterator it = tnode.begin(); it != tnode.end(); it++) {
opt[*it] = max(opt[*it],size[u]-size[*it]) ;
if(opt[*it] < mi) {
mi = opt[*it];
ans = *it;
}
}
return ans;
}
vector<int> all ;
void Get_Dis(int u,int len,int dep,int fa)
{
now.push_back(make_pair(len,dep));
for(vector<Edge>::iterator it = E[u].begin(); it != E[u].end(); it++) {
if(!Del[it->v] && it->v != fa) {
Get_Dis(it->v,len+it->w,dep+1,u);
}
}
}
inline void Merge(vector<pair<int,int> > a)
{
for(vector<pair<int,int> >::iterator it = a.begin(); it != a.end(); it++) {
if(it->first<=K) {
all.push_back(it->first);
Update(dp[it->first],it->second);
}
}
}
void Solve(int u)
{
u = Get_Root(u);
all.clear();
int nch = 0;
dp[0] = 0;
for(vector<Edge>::iterator it = E[u].begin(); it != E[u].end(); it++) {
if(!Del[it->v]) {
nch ++;
now.clear();
Get_Dis(it->v,it->w,1,u);
Calc(now);
Merge(now);
}
}
for(vector<int>::iterator it = all.begin(); it != all.end(); it++) {
dp[*it] = -1;
}
Del[u] = true;
for(vector<Edge>::iterator it = E[u].begin(); it != E[u].end(); it++) {
if(!Del[it->v]) {
Solve(it->v);
}
}
}
inline void Calc(vector<pair<int,int> >now)
{
for(vector<pair<int,int> >::iterator it = now.begin(); it != now.end(); it++) {
if(it->first <= K ) {
if(dp[K-it->first] != -1) {
Update(Ans,dp[K-it->first]+it->second);
}
}
}
}
inline void Update(int &x,int cmp)
{
if(x==-1 || x > cmp) x = cmp;
}
void Init()
{
int a,b,c;
Ans = -1;
scanf("%d%d",&N,&K);
fill(dp,dp+K+1,-1);
for(int i = 1; i < N; i++)
{
scanf("%d%d%d",&a,&b,&c);
a++ ; b++;
E[a].push_back(Edge(b,c));
E[b].push_back(Edge(a,c));
}
}
int Ans;
}sol;
int main()
{
sol.Init();
sol.Solve(1);
printf("%d\n",sol.Ans);
return 0;
}
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 222222;
struct Divided_Conquer {
struct Edge{
int v , w;
Edge(){}
Edge(int v,int w): v(v),w(w) {
}
};
bool Del[maxn];
vector<Edge> E[maxn];
int N , K;
int size[maxn] , opt[maxn] ,dp[1000010];
vector<int> tnode ;
vector<pair<int,int> > now;
void Dfs(int u,int f)
{
tnode.push_back(u);
size[u] = 1;
opt[u] = 0;
for(vector<Edge>::iterator it = E[u].begin(); it != E[u].end(); it++) {
if(!Del[it->v] && it->v != f) {
Dfs(it->v,u);
size[u] += size[it->v];
opt[u] = max(opt[u],size[it->v]);
}
}
}
int Get_Root(int u)
{
tnode.clear();
Dfs(u,-1);
int mi = maxn , ans = -1;
for(vector<int>::iterator it = tnode.begin(); it != tnode.end(); it++) {
opt[*it] = max(opt[*it],size[u]-size[*it]) ;
if(opt[*it] < mi) {
mi = opt[*it];
ans = *it;
}
}
return ans;
}
vector<int> all ;
void Get_Dis(int u,int len,int dep,int fa)
{
now.push_back(make_pair(len,dep));
for(vector<Edge>::iterator it = E[u].begin(); it != E[u].end(); it++) {
if(!Del[it->v] && it->v != fa) {
Get_Dis(it->v,len+it->w,dep+1,u);
}
}
}
inline void Merge(vector<pair<int,int> > a)
{
for(vector<pair<int,int> >::iterator it = a.begin(); it != a.end(); it++) {
if(it->first<=K) {
all.push_back(it->first);
Update(dp[it->first],it->second);
}
}
}
void Solve(int u)
{
u = Get_Root(u);
all.clear();
int nch = 0;
dp[0] = 0;
for(vector<Edge>::iterator it = E[u].begin(); it != E[u].end(); it++) {
if(!Del[it->v]) {
nch ++;
now.clear();
Get_Dis(it->v,it->w,1,u);
Calc(now);
Merge(now);
}
}
for(vector<int>::iterator it = all.begin(); it != all.end(); it++) {
dp[*it] = -1;
}
Del[u] = true;
for(vector<Edge>::iterator it = E[u].begin(); it != E[u].end(); it++) {
if(!Del[it->v]) {
Solve(it->v);
}
}
}
inline void Calc(vector<pair<int,int> >now)
{
for(vector<pair<int,int> >::iterator it = now.begin(); it != now.end(); it++) {
if(it->first <= K ) {
if(dp[K-it->first] != -1) {
Update(Ans,dp[K-it->first]+it->second);
}
}
}
}
inline void Update(int &x,int cmp)
{
if(x==-1 || x > cmp) x = cmp;
}
void Init()
{
int a,b,c;
Ans = -1;
scanf("%d%d",&N,&K);
fill(dp,dp+K+1,-1);
for(int i = 1; i < N; i++)
{
scanf("%d%d%d",&a,&b,&c);
a++ ; b++;
E[a].push_back(Edge(b,c));
E[b].push_back(Edge(a,c));
}
}
int Ans;
}sol;
int main()
{
sol.Init();
sol.Solve(1);
printf("%d\n",sol.Ans);
return 0;
}
