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

p;
}
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
#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 = 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;
}

BZOJ 2599 Race 点的分治 (二)