description
今有一边带权的树,求其直径，并求其所有直径经过公共边的条数.
solution
本题主要考察树的直径的性质.对于第一问,相信都能做,这里重点讨论第二问.这里,我们介绍两个引理:
引理一:如果一棵树有多条直径,那么它们必有公共边.
这里用反证法证明.假设树有两条直径(xi(x,y))和(xi(u,v)),其长均为(d).若它们没有公共边,则设(xi(alpha,eta))为两条直径上距离最短的两个点间的路径,则有(max(|xi(x,alpha)|,|xi(y,alpha)|)geq frac{d}{2},max(|xi(u,eta)|,|xi(v,eta)|)geq frac{d}{2}),则有(max(|xi(x,alpha)|,|xi(y,alpha)|)+max(|xi(u,eta)|,|xi(v,eta)|)+|xi(alpha,eta)|>d),与(xi(x,y))和(xi(u,v))是树的直径相矛盾,故树的多条直径间必有公共边.证毕.
引理二:在引理一的基础上,树的多条直径间的公共边是连续的.
这里交给读者证明.
在这两个引理的基础上,我们可以先求出树直径的两个端点,再从左往右扫一遍,找出最右侧的不可能成为必经边的端点.再从右往左扫一遍,找出最左侧不可能成为必经边的点.最后统计答案即可.具体见代码.
code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<map>
#define R register
#define next jfklslk
#define debug puts("mlg")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
inline ll read();
inline void write(ll x);
inline void writesp(ll x);
inline void writeln(ll x);
ll n;
ll head[1000000],next[1000000],tot,to[1000000];
ll w[1000000];
inline void add(ll x,ll y,ll z){to[++tot]=y;next[tot]=head[x];head[x]=tot;w[tot]=z;}
ll l,r;
ll maxn,d[1000000],pre[1000000];
inline void dfs1(ll x,ll fa,ll deep,bool type){
d[x]=deep;
pre[x]=fa;
if(d[x]>maxn){
maxn=d[x];
if(type) r=x;
else l=x;
}
for(R ll i=head[x],ver;i;i=next[i]){
ver=to[i];
if(ver==fa) continue;
dfs1(ver,x,deep+w[i],type);
}
}
bool vis[1100000],book[1100000];
ll dis[1100000],val[1100000];
ll nxt[1100000];
ll maxx;
inline void dfs2(ll x,ll fa,ll deep){
dis[x]=deep;
maxx=max(maxx,dis[x]);
for(R ll i=head[x],ver;i;i=next[i]){
ver=to[i];
if(ver==fa||book[ver]) continue;
dfs2(ver,x,deep+w[i]);
}
}
ll l1,r1;
ll ans;
ll cnt;
int main(){
n=read();
for(R ll i=1,x,y,z;i<n;i++){
x=read();y=read();z=read();
add(x,y,z);add(y,x,z);
}
dfs1(1,0,0,0);
maxn=0;
dfs1(l,0,0,1);
writeln(maxn);
for(R ll x=r;x;x=pre[x]) book[x]=true,nxt[pre[x]]=x,++cnt;
for(R ll x=r;x;x=pre[x]){
maxx=0;
dfs2(x,0,0);
val[x]=maxx;
}
for(R ll x=l;x;x=nxt[x]){
if(val[x]==maxn-d[x]){
r1=x;break;
}
}
for(;r1!=0;r1=pre[r1]){
if(val[r1]==d[r1]) break;
++ans;
}
writeln(ans);
}
inline ll read(){ll x=0,t=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') t=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*t;}
inline void write(ll x){if(x<0){putchar('-');x=-x;}if(x<=9){putchar(x+'0');return;}write(x/10);putchar(x%10+'0');}
inline void writesp(ll x){write(x);putchar(' ');}
inline void writeln(ll x){write(x);putchar('
');}