BZOJ 2599 Race 点的分治 - c++编程基础

题意：给一棵树,每条边有权.求一条路径,权值和等于K,且边的数量最小. （我会告诉你这就是题面？）

BZOJ的题就是好啊！一句话题意，赞一个。

这道题的思路还是点分治，类似于前面那篇文章里的两题，只不过转换成了求最小而不是计数，，，

每次找好重心u后，我们只考虑以u为根的子树，u的子树可以分治下去搞。

我们只考虑经过根的路径

由前面两题，可以很轻松的想到这样一个方法：

先搜出当前树所有的二元组（W,Dep），然后排序，扫描，但是注意，有可能两个点来自于同一棵子树，如果给二元组加一个信息属于哪颗子树，就变成了三元组。。。。判断两个元素是否满足条件需要满足三个信息，很是复杂啊。。不过我还是用这个方法写了老半天，最后实在搞不定就想其他方法了。

还是由以前做过的一些树形DP得到的启发，我们一棵一棵子树的去合并，也就是在当前子树找一个点（w,dep），在前面的子树找一个点，这个点

到根的权值和是 K-W ，并且深度最小，我们就记为dp[K-w]好了，（这种方法在合并子树的问题上还是蛮常用的），然后我们每次先询问再更新DP数组就好了，要注意DP数组的初始化，不能全部都清空，要不果断TLE。。。。

这题的数据应该还是蛮好造的吧。。。。

附上代码：速度略慢啊，跑了17s多

[cpp]
#include
#include
#include
#include
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 E[maxn];
int N , K;
int size[maxn] , opt[maxn] ,dp[1000010];
vector tnode ;
vector > now;
void Dfs(int u,int f)
{
tnode.push_back(u);
size[u] = 1;
opt[u] = 0;
for(vector::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::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 all ;
void Get_Dis(int u,int len,int dep,int fa)
{
now.push_back(make_pair(len,dep));
for(vector::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 > a)
{
for(vector >::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::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::iterator it = all.begin(); it != all.end(); it++) {
dp[*it] = -1;
}
Del[u] = true;
for(vector::iterator it = E[u].begin(); it != E[u].end(); it++) {
if(!Del[it->v]) {
Solve(it->v);
}
}
}
inline void Calc(vector >now)
{
for(vector >::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 = cm

BZOJ 2599 Race 点的分治 (一)