[bzoj3124] [Sdoi2013]直径

  看了child学长的题解才知道怎么写TAT

  http://www.cnblogs.com/ctlchild/p/5160272.html

  以前不知道直径都是过重心的。。代码改着改着就和标程完全一样了QAQ

 #include<cstdio>
#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
const int maxn=;
struct zs{
int too,pre,dis;
}e[maxn<<];int tot,last[maxn];
int sz[maxn],fa[maxn],mx[maxn],bel[maxn],dep[maxn];
ll dis[][maxn],len;
int rt,st1[maxn],st2[maxn],top1,top2;
int i,j,k,n,m,a,b; int ra;char rx;
inline int read(){
rx=getchar(),ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
inline int max(int a,int b){return a>b?a:b;} inline void insert(int a,int b,int c){
e[++tot].too=b,e[tot].dis=c,e[tot].pre=last[a],last[a]=tot;
e[++tot].too=a,e[tot].dis=c,e[tot].pre=last[b],last[b]=tot;
}
inline void dfs(int x,int id){
sz[x]=;mx[x]=;dep[x]=dep[fa[x]]+;
for(register int i=last[x];i;i=e[i].pre)if(e[i].too!=fa[x])
dis[id][e[i].too]=e[i].dis+dis[id][x],fa[e[i].too]=x,
dfs(e[i].too,id),
sz[x]+=sz[e[i].too],mx[x]=max(mx[x],sz[e[i].too]);
mx[x]=max(mx[x],n-sz[x]);
}
inline void dfs1(int x){
dep[x]=dep[fa[x]]+;
for(register int i=last[x];i;i=e[i].pre)if(e[i].too!=fa[x])
fa[e[i].too]=x,dfs1(e[i].too);
}
inline void dfs2(int x,int chain){
register int i,pos=;bel[x]=chain;
for(i=last[x];i;i=e[i].pre)if(e[i].too!=fa[x]&&sz[e[i].too]>sz[pos])pos=e[i].too;
if(!pos)return;
dfs2(pos,chain);
for(i=last[x];i;i=e[i].pre)if(e[i].too!=fa[x]&&e[i].too!=pos)dfs2(e[i].too,e[i].too);
}
inline int getlca(int a,int b){
while(bel[a]!=bel[b]){
if(dep[bel[a]]<dep[bel[b]])swap(a,b);
a=fa[bel[a]];
}
return dep[a]<dep[b]?a:b;
}
int main(){
register int i;
n=read();
for(i=;i<n;i++)a=read(),b=read(),insert(a,b,read());
int s,t;
fa[]=,dfs(,);for(i=,s=;i<=n;i++)if(dis[][i]>dis[][s])s=i;
fa[s]=,dfs(s,);for(i=,t=;i<=n;i++)if(dis[][i]>dis[][t])t=i;
len=dis[][t];printf("%lld\n",len);
fa[t]=,dis[][t]=,
dfs(t,);
for(i=;i<=n;i++){
if(dis[][i]==len&&dis[][i]==len){puts("");return ;}
if(dis[][i]==len)st1[++top1]=i;
if(dis[][i]==len)st2[++top2]=i;
}
for(i=rt=;i<=n;i++)if(mx[i]<mx[rt])rt=i;
fa[rt]=,dfs1(rt);dfs2(rt,rt);
for(a=st1[],i=;i<=top1&&a!=rt;i++)a=getlca(a,st1[i]);
for(b=st2[],i=;i<=top2&&b!=rt;i++)b=getlca(b,st2[i]);
printf("%d\n",dep[a]+dep[b]-dep[getlca(a,b)]*);
return ;
}
上一篇:PHPcms 系统简单使用


下一篇:Laravel5路由/home页面无法访问