| 路径(2015升级版) |
| 难度级别：D； 运行时间限制：1000ms； 运行空间限制：262144KB； 代码长度限制：2000000B |
|
试题描述
|
|
WZJ在生日当天决定在他的领地举行一场马拉松比赛，他的领地有N座城市，是通过道路相连组成了一个N-1条边的无向无环图。每条边由ai连到bi，距离为ci。WZJ决定选取两个城市分别为起点和终点，举行比赛。比赛时按这两个城市间的最短距离进行比赛。WZJ想选出一条尽量长的路径，但由于资金限制，路径长最多不能超过k。你能帮帮他吗？
|
|
输入
|
|
第一行为两个正整数N，k，表示N个城市,最长距离为K。
接下来N-1行为ai,bi,ci，表示有一条边从ai到bi，距离为ci。 |
|
输出
|
|
输出路径在小于k的情况下的最长长度。
|
|
输入示例
|
|
5 7
1 2 3 1 3 4 4 5 7 4 2 2 |
|
输出示例
|
|
7
|
|
其他说明
|
|
1<=N<=50000
1<=ai,bi<=N 1<=ci<=k<=10^9 起点为2，终点为3. 放心，不是O(nlog^2n)是过不了的！ |
题解：点分治，看好那个find函数。。。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#include<ctime>
#define PAU putchar(' ')
#define ENT putchar('\n')
#define CH for(int d=0;d<2;d++)if(ch[d])
using namespace std;
const int maxn=+,maxm=+,inf=-1u>>;
struct node{
node*ch[];int r,siz,v;
void init(){r=rand();siz=;ch[]=ch[]=NULL;return;}
void update(){siz=;CH{siz+=ch[d]->siz;}return;}
}treap[maxn],*nodecnt=treap,*root;queue<node*>R;
void del(node*&x){R.push(x);x=NULL;return;}
void deltree(node*&x){
if(!x)return;deltree(x->ch[]);deltree(x->ch[]);del(x);return;
}
node*newnode(){
node*k;if(R.empty())k=nodecnt++;else k=R.front(),R.pop();k->init();return k;
}
void rotate(node*&x,int d){
node*k=x->ch[d^];x->ch[d^]=k->ch[d];k->ch[d]=x;x->update();k->update();x=k;return;
}
void insert(node*&x,int v){
if(!x)x=newnode(),x->v=v;
else{int d=v>x->v;insert(x->ch[d],v);
if(x->r<x->ch[d]->r)rotate(x,d^);else x->update();
}return;
}
void print(node*x){
if(!x)return;print(x->ch[]);printf("%d ",x->v);print(x->ch[]);return;
}
int find(node*x,int v){
if(!x)return ;
if(v==x->v)return v;
if(v>x->v)return max(x->v,find(x->ch[],v));
return find(x->ch[],v);
}
struct ted{int x,y,w;ted*nxt;}adj[maxm],*fch[maxn],*ms=adj;
void add(int x,int y,int w){
*ms=(ted){x,y,w,fch[x]};fch[x]=ms++;
*ms=(ted){y,x,w,fch[y]};fch[y]=ms++;
return;
}
int ans,k,t[maxn],cnt,f[maxn],CG,siz[maxn],size;bool vis[maxn];
void findcg(int x,int fa){
siz[x]=;int mxs=;
for(ted*e=fch[x];e;e=e->nxt){
int v=e->y;if(v!=fa&&!vis[v]){
findcg(v,x);siz[x]+=siz[v];mxs=max(mxs,siz[v]);
}
}f[x]=max(mxs,size-siz[x]);if(f[x]<f[CG])CG=x;return;
}
void dfs(int x,int fa,int dis){
siz[x]=;t[cnt++]=dis;
for(ted*e=fch[x];e;e=e->nxt){
int v=e->y;if(v!=fa&&!vis[v])dfs(v,x,dis+e->w),siz[x]+=siz[v];
}return;
}
void solve(int x){
vis[x]=true;insert(root,);
for(ted*e=fch[x];e;e=e->nxt){
int v=e->y;if(!vis[v]){
cnt=;dfs(v,x,e->w);
for(int i=;i<cnt&&t[i]<=k;i++)ans=max(ans,find(root,k-t[i])+t[i]);
for(int i=;i<cnt;i++)insert(root,t[i]);
}
}deltree(root);
for(ted*e=fch[x];e;e=e->nxt){
int v=e->y;if(!vis[v]){
f[CG=]=size=siz[v];findcg(v,x);solve(CG);
}
}return;
}
inline int read(){
int x=,sig=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')sig=-;ch=getchar();}
while(isdigit(ch))x=*x+ch-'',ch=getchar();
return x*=sig;
}
inline void write(int x){
if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;
int len=,buf[];while(x)buf[len++]=x%,x/=;
for(int i=len-;i>=;i--)putchar(buf[i]+'');return;
}
int n;
void init(){
srand(time());
n=read();k=read();int x,y;
for(int i=;i<n;i++)x=read(),y=read(),add(x,y,read());
f[CG=]=size=n;findcg(,);solve(CG);write(ans);
return;
}
void work(){
return;
}
void print(){
return;
}
int main(){init();work();print();return ;}
/*
5 8
1 2 2
2 3 7
1 4 3
4 5 4
*/