bzoj2599: [IOI2011]Race 点分治

83 阅读 0 评论 55 点赞

我是靠谱客的博主伶俐荷花，最近开发中收集的这篇文章主要介绍bzoj2599: [IOI2011]Race 点分治，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：给一棵树,每条边有权.求一条简单路径,权值和等于K,且边的数量最小.N <= 200000, K <= 1000000

明显点分治，但是愚蠢的我并没有想到怎么分治。。%hzwer。
开一个t[i]表示整棵树中权值和为i的路径有多少条，那么我们分治每一颗树的时候，再算出子节点到当前根的dis[x]权值距离和d[x]点数距离，然后就可以直接更新了ans=min(ans,t[k-dis[x]]+d[x]);
然后再更新dis和d，因为如果先更新了就会算重，有一种情况，即起点终点在子树内但是经过了根，这样就会算重复了。。
注意inf设小一点，不然会爆int。。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=4e5+5;
const int M=1e6+5;