题意：
给你一个有n个点的树,给定根,叫你找第k大的特殊链 。
特殊的链的定义:u,v之间的路径,经过题给的根节点.
题解：(来自BC官方题解)
对于求第k大的问题，我们可以通过在外层套一个二分，将其转化为求不小于mid的有多少个的问题。
接下来我们讨论如何求树上有多少条折链的长度不小于k。
我们考虑常规的点分治（对于重心，求出其到其他点的距离，排序+单调队列），时间复杂度为O(nlog^2n)，但是这只能求出普通链的数量。
我们考虑将不属于折链的链容斥掉。也即，我们需要求出有多少条长度不小于mid的链，满足一端是另一端的祖先。设有一条连接u,v的链,u是v的祖先。
我们设d[i]为从根到i的链的长度，然后枚举v，然后计算在从根到v的链上，有多少个点i满足d[v]−dist[i]≥mid
我们可以按照dfs序访问各结点，动态维护从根到其的链上各d值构成的权值树状数组，就能够计算这种链的数量。时间复杂度为O(nlogn)。 因此求长度不小于mid的折链数量可以在O(nlog2n)的时间复杂度内完成。再套上最外层的二分，总时间复杂度为O(nlog3n)。
n的范围是50000，时限6s，卡常数就过去了（本行划线 由于在点分治中，复杂度中第二个logn的瓶颈在于排序。由于每次排序都是对相同的数排序，因此我们可以考虑将点分治+排序作为预处理，每次二分的时候只要做单调队列部分即可。
上述做法的总时间复杂度为O(nlog2n)。
#include<bits/stdc++.h>
#define F(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int N=1e5+; int T,n,m,k,g[N],nxt[N],v[N*],w[N*],ed,C[N*],hsh_ed,hsh[*N];
int sz[N],vis[N],mx[N],mi,ROOT,root,idx,ret,cnt;
vector<int>G[N*],G_rt[N]; void adg(int x,int y,int c){v[++ed]=y,w[ed]=c,nxt[ed]=g[x],g[x]=ed;}
inline void up(int &a,int b){if(a<b)a=b;} inline void add(int x,int c){while(x<=hsh_ed)C[x]+=c,x+=x&-x;}
inline int ask(int x){int an=;while(x>)an+=C[x],x-=x&-x;return an;}
inline int getid(int x){return lower_bound(hsh+,hsh++hsh_ed,x)-hsh;} void get_rt(int u,int fa,int num)
{
sz[u]=,mx[u]=;
for(int i=g[u];i;i=nxt[i])
if(v[i]!=fa&&!vis[v[i]])
get_rt(v[i],u,num),sz[u]+=sz[v[i]],up(mx[u],sz[v[i]]);
up(mx[u],num-sz[u]);
if(mx[u]<mi)mi=mx[u],root=u;
} void get_dis(int u,int fa,int dis)
{
G[cnt].push_back(dis);
for(int i=g[u];i;i=nxt[i])
if(v[i]!=fa&&!vis[v[i]])
get_dis(v[i],u,dis+w[i]);
} void init_cal(int u,int dis)
{
cnt++,get_dis(u,u,dis);
sort(G[cnt].begin(),G[cnt].end());
} void get_all(int u)
{
init_cal(u,),vis[u]=;
for(int i=g[u];i;i=nxt[i])
if(!vis[v[i]])
{
init_cal(v[i],w[i]);
mi=sz[v[i]],get_rt(v[i],v[i],sz[v[i]]);
G_rt[u].push_back(root);
get_all(root);
}
} void init_tree()
{
F(i,,n)G_rt[i].clear();
F(i,,*n)G[i].clear();
memset(vis,,sizeof(vis));
mi=n,get_rt(,,n),ROOT=root;
cnt=,get_all(ROOT);
}
//----------------以上为预处理-------- int cal(int mid)
{
int an=;
int i=,j=G[++idx].size()-;
while(i<j)
{
while(j>i&&G[idx][j]+G[idx][i]<mid)i++;
an+=j-i,j--;
}
return an;
} void work(int u,int mid)//求出所有的链
{
ret+=cal(mid),vis[u]=;
int sz=G_rt[u].size()-;
F(i,,sz)ret-=cal(mid),work(G_rt[u][i],mid);
} void dfs(int u,int fa,int dis,int mid)//将每个点过根的距离计算出来
{
hsh[++hsh_ed]=dis,hsh[++hsh_ed]=dis-mid;
for(int i=g[u];i;i=nxt[i])
if(v[i]!=fa)dfs(v[i],u,dis+w[i],mid);
} void get_ret(int u,int fa,int dis,int mid)//容斥不经过根节点的答案
{
int x=getid(dis-mid),y=getid(dis);
ret-=ask(x),add(y,);
for(int i=g[u];i;i=nxt[i])
if(v[i]!=fa)
get_ret(v[i],u,dis+w[i],mid);
add(y,-);
} int check(int mid)
{
ret=,memset(vis,,sizeof(vis));
idx=,work(ROOT,mid);
hsh_ed=,dfs(m,m,,mid);
sort(hsh+,hsh++hsh_ed);
hsh_ed=unique(hsh+,hsh++hsh_ed)-hsh-;
get_ret(m,,,mid);
if(ret>=k)return ;
return ;
} int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&m,&k);
int maxdis=;
memset(g,,sizeof(g)),ed=;
F(i,,n-)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
adg(x,y,c),adg(y,x,c);
up(maxdis,c);
}
init_tree();
int l=,r=maxdis*n,ans=,mid;
while(l<=r)
{
mid=l+r>>;
if(check(mid))ans=mid,l=mid+;
else r=mid-;
}
if(!ans)puts("NO");
else printf("%d\n",ans);
}
return ;
}