围观了final，SJTU还是飞了,泽民同志劲啊!
膜拜归膜拜...回来开题
bzoj1999树网的核
最近就喜欢给自己找切不动的题...QAQ
ok.....昨天在家里做了一个下午+晚上 又困&又累，虽然的确是调出了一些bug但是最sb的一句话今天才刚刚调出来...晕啊
finding my 状态ing...
联赛数据n=300,现在想想真是厚道,vijos也很厚道,一个完全通不过的程序居然还A了...
Demi Guo说过思考三部曲,想法是什么,想法怎么来的,我为什么想不到.
(证明一)核一定存在于直径上,并且存在于任何一条直径上.这个证明网上blog有很多,我贴一个我看过的.
第一步自然是找直径。我们实在是很想用Floyd来求直径，但N=300的范围在那里摆着，迫使我们要寻求更快的方法。我们注意到直径的一个性质：
对于直径中的任意一点，其距离树中其他点的最远距离不超过该点到达直径端点的距离。这是个显而易见的性质。由这个性质，我们可以导出如下引理：
对于树中的任意一点，距离其最远的点一定是树的直径的某一端点。
用同样的方法，我们很容易找到另一个端点，也就求出了直径。现在的问题是：直径可能有很多条，究竟取哪一条呢？其实任意一条都是可行的。我们做如下的说明：
首先，题目中告诉我们树的所有直径的中点必然重合，也就是告诉我们：所有的直径都是相交的。从而对于任意两条不同的直径，我们可以找到一个分叉点，我们记分叉部分的长度为L1，直径总长减去L1的长度记为L2。假设这个“核”没有经过分叉点，那么两种情况：
1、 在公共部分，其最小“偏心距”一定不大于L2；
2、 在分叉部分，其最小“偏心距”一定不小于L2。
假设这个“核”经过分叉点，那么其最小偏心距至少是L1。所以很明显，其最小“偏心距”所对应的“核”必然有一部分出现在所有直径的公共部分，而对于不完全在公共部分的“核”，其“偏心距”拥有同样的下界L1，也不会影响到最终结果。
还有一个比较形象直观的证明,传送门:http://blog.csdn.net/cyxhahaha/article/details/47345999
(证明二)核找得越长越好,这个很好理解.
在找核的时候,大家都用了单调队列,我比较弱..个人感觉rmq好理解..然后MLE...又辛辛苦苦地改成了线段树...
时间慢不多说
#include<cstdio>
#include<algorithm>
#define inf 1<<30
#define N 500100
using namespace std;
],vet[N*],pri[N*],u[N],arr[N],q[N*];
][],dis[][N],tree[N*];
void bfs(int st,int ed,int id)
{
,r=,now;q[]=st;u[st]=;dis[id][st]=;
while(l<=r)
{
now=q[l];int e=head[now];
)
{
int v=vet[e];
){
r++;q[r]=v;dis[id][v]=dis[id][now]+pri[e];u[v]=;
)if(v==ed)break;
}
e=next[e];
}
)if(q[r]==ed)break;
l++;
}
;i<=n;i++)u[i]=;
)
{
num[]=ed;num[]=;arr[ed]=;
;i;i--)][q[i]]+dis[][q[i]]==dis[][st]){//跟posa距离+跟posb距离==posa-posb
++num[];num[num[]]=q[i];arr[q[i]]=;
}
}
}
void add(int u,int v,int w)
{
edgenum++;vet[edgenum]=v;next[edgenum]=head[u];head[u]=edgenum;pri[edgenum]=w;
}
void bii(int x)
{
//printf("dis===%d\n",x);
u[x]=;int e=head[x];
)
{
int v=vet[e];
&&u[v]==)
{
bii(v);
f[x][]=max(f[x][],f[v][]+pri[e]);
}
e=next[e];
}
}
void update(int l,int r,int st,int ed,int p,int v)
{
if(l==st&&r==ed){
tree[p]=v;return;}
;
,ed,p+p+,v);else {
update(l,mid,st,mid,p+p,v);update(mid+,r,mid+,ed,p+p+,v);
}
])tree[p]=tree[p+p];];
}
int find(int l,int r,int st,int ed,int p)
{
if(l==st&&r==ed)return tree[p];
;
if(r<=mid)return find(l,r,st,mid,p+p);else
,ed,p+p+);else
,r,mid+,ed,p+p+));
}
int query(int st,int ed)
{
,k=;
tmp=find(st,ed,,num[],);
return tmp;
}
int main()
{
freopen("1999.in","r",stdin);
scanf("%d%d",&n,&s);int uu,vv,ww;
;i<=n-;i++)
{
scanf("%d%d%d",&uu,&vv,&ww);add(uu,vv,ww);add(vv,uu,ww);
}
bfs(,,);posa=;dis[][]=-;;i<=n;i++)][i]>dis[][posa])posa=i;
bfs(posa,,);posb=;dis[][]=-;;i<=n;i++)][i]>dis[][posb])posb=i;
bfs(posb,posa,);
//printf("%d %d\n",posa,posb);
;i<=num[];i++)bii(num[i]);
;i<=num[];i++)update(i,i,,num[],,f[num[i]][]);
,r=;int ans=inf;
//printf("dis===%d\n",f[2][0]);
])
{
r=max(r,l);
<=num[]&&(dis[][num[r+]]-dis[][num[l]])<=s)
{
r++;
}
ans=min(ans,max(dis[][posb]-dis[][num[r]],max(dis[][num[l]],query(l,r))));
l++;
}
printf("%d",ans);
}