题目
题目大意
给你带边权的树，然后有多高询问，每次询问距离某个点第近的节点的距离。
思考
一眼看下去，首先就是想到如何动态的区间第K大，还要支持区间修改……
于是想了半天，觉得不可做……
最终在无奈之下看了题解
正解
这题需要用到点分治。
什么是点分治？
网上的解释一堆，我就随便解释一下：
对于一棵树，找出它的重心，然后分成许多棵子树，然后在这些子树中继续进行分治。
这样分治顶多有层，所以点分治的时间复杂度是的。
至于为什么……
我们知道一棵树的重心，它的最大子树是最小的。
所以，每一棵子树的大小不可能大于整棵树的一半（不然这个重心会调整）。
然后就是这样了……
点分治之后，就可以形成一个抽象的点分树。
每个点都会管辖一定的范围。
首先，我们可以二分一下答案，接着问题转化成和这个点的距离小于的答案个数。
对于每个点，我们可以处理出它所管辖的范围内的所有点到它的距离，并且将这些距离排序。这样，我们计算它们的贡献时就可以二分了。
在统计答案时，首先先统计这个点对答案的贡献，然后跳到它在点分树上的父亲，再到爷爷……
不过有一点要切记，从这个点跳到父亲前，必须将这个范围的对父亲的贡献的影响减去。同样的，我们减去这个影响也利用了二分。
然后这道题就解决了。
然而不要高兴得太早，因为代码很长……（第一次打点分治打得很丑）
具体细节见程序。
代码
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define MAXN 50000
#define MAXM 50000
int n,m;
struct EDGE{
int to,len;
EDGE *las;
bool cut;//这个变量是用来辅助建立点分树的。标记过后相当于这条边被裁掉，表明两边不在同一管辖区域内
} e[MAXN*2+1];
int ne=-1;
EDGE *last[MAXN+1];
#define rev(ei) (e+(int(ei-e)^1))//表示反向边
inline void link(int u,int v,int len){
e[++ne]={v,len,last[u],0};
last[u]=e+ne;
}
int fat[MAXN+1],itf[MAXN+1];//fat就是father，表示点分树上的父亲；itf表示的是一个对应的东西，详见下文
int siz[MAXN+1];//子树大小，计算重心中需要用到
vector<int> dis[MAXN+1],dis2[MAXN+1];//dis表示它到管辖的范围到它的距离，dis2表示它所管辖的范围对它父亲的影响（用dis2[itf[x]]表示）
int cnt;//一个用来分配dis2的东西，详见下文
void maketree(int,int,int);//建立点分树
int ok(int,int);//ok(u,lim)//表示和u的距离小于等于lim的点数（包括u自己）
//以下是倍增LCA，根节点设为1
int dep[MAXN+1],fa[MAXN+1][17],sum[MAXN+1];//sum表示1到它的距离（用以差分计算两点间的距离）
void init_lca(int x){
siz[x]=1;
for (int i=1;1<<i<dep[x];++i)
fa[x][i]=fa[fa[x][i-1]][i-1];
for (EDGE *ei=last[x];ei;ei=ei->las)
if (ei->to!=fa[x][0]){
fa[ei->to][0]=x;
sum[ei->to]=sum[x]+ei->len;
dep[ei->to]=dep[x]+1;
init_lca(ei->to);
siz[x]+=siz[ei->to];//顺便将第一次的siz数组处理一下
}
}
int lca(int u,int v){
if (dep[u]<dep[v])
swap(u,v);
for (int k=dep[u]-dep[v],i=0;k;k>>=1,++i)
if (k&1) u=fa[u][i];
if (u==v)
return u;
for (int i=15;i>=0;--i)
if (fa[u][i]!=fa[v][i])
u=fa[u][i],v=fa[v][i];
return fa[u][0];
}
int main(){
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<n;++i){
int u,v,len;
scanf("%d%d%d",&u,&v,&len);
link(u,v,len),link(v,u,len);
}
init_lca(1);
maketree(1,0,cnt=1);
for (int i=1;i<=m;++i){
int u,k;
scanf("%d%d",&u,&k);
int l=1,r=500000000,res=0;
while (l<=r){
int mid=l+r>>1;
if (ok(u,mid)>k)//由于包括u自己，所以是“>”
r=(res=mid)-1;
else
l=mid+1;
}
printf("%d
",res);
}
return 0;
}
int find_hvy(int x,int fa,int all){//找重心 （all为整棵树的大小）
int mx=all-siz[x];//表示最大的子树
for (EDGE *ei=last[x];ei;ei=ei->las)
if (!ei->cut && ei->to!=fa){
int k=find_hvy(ei->to,x,all);
if (k)
return k;
mx=max(mx,siz[ei->to]);
}
if (mx<=all>>1)//这是重心的一个性质：最大的子树不超过总数的一半
return x;
return 0;
}
void get_dist(vector<int> &dis,vector<int> &dis2,int x,int fa,int di){//处理距离
dis.push_back(di);
dis2.push_back(di);
siz[x]=1;
for (EDGE *ei=last[x];ei;ei=ei->las)
if (!ei->cut && ei->to!=fa){
get_dist(dis,dis2,ei->to,x,di+ei->len);
siz[x]+=siz[ei->to];//顺便将siz处理一下
}
}
void maketree(int x,int fa,int num){
int hvy=find_hvy(x,fa,siz[x]);//可以直接寻找重心的原因是siz早在之前就处理过了
itf[hvy]=num;//itf表示它对应的dis2的编号
fat[hvy]=fa;
dis[hvy].push_back(0);
for (EDGE *ei=last[hvy];ei;ei=ei->las)
if (!ei->cut){
cnt++;//新分配一个vector
get_dist(dis[hvy],dis2[cnt],ei->to,hvy,ei->len);//处理好它自己的dis，并且处理儿子对它的影响，一举两得
sort(dis2[cnt].begin(),dis2[cnt].end());
rev(ei)->cut=1;
maketree(ei->to,hvy,cnt);
}
sort(dis[hvy].begin(),dis[hvy].end());
}
int ok(int x,int k){
int start=x,res=0;
for (int lim=k;x;x=fat[x]){
vector<int>::iterator p=upper_bound(dis[x].begin(),dis[x].end(),lim);
res+=int(p-dis[x].begin());//记录它的贡献
lim=k-(sum[fat[x]]+sum[start]-(sum[lca(fat[x],start)]<<1));//减去这个点父亲和起始点的距离（因为要算上起始点走到它要经过的路程）
if (fat[x]){
p=upper_bound(dis2[itf[x]].begin(),dis2[itf[x]].end(),lim);
res-=int(p-dis2[itf[x]].begin());//减去它对父亲的影响
}
}
return res;
}
总结
lyl说，普通的点分治，需要在父亲中减去它本身的贡献，以达到去重的目的。