# Bzoj3124: [sdoi2013] diameter

2020-12-07 14:26:09

solution ：
Two silly conclusions ：
First of all, it must be on the same diameter . Because every diameter goes through this section .
It must be a continuous segment .
Because if you have two paragraphs . So how did you get there （ There are only two paths on the tree ！）

In this way, it's easy to do .
Whatever diameter .
Determine a path on this diameter . Make this path ：
It's impossible at any point to extend a diameter from another branch .
I don't want to draw pictures and describe them directly .
Suppose we find a diameter that is 1->2->5->7
So from 2 Start asking （ because 1 There must be no son , Otherwise it won't be the end of the diameter ）
So we can record 1 To 2 Distance of , Assuming that t.
And then look at it 2 Can we walk a distance from other branches t. If you can, then 2 None of the previous edges are at the intersection of all diameters

Asked about 5 Just record 1 To 5 Distance of , Assuming that T.
And then look at it 5 Can you come out of another branch T. If you can, then 5 It's not even good on the side before .
And so on .

We've determined the scope .
Then we can solve the problem .

Code implementation ：

``````#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
struct node {

int x,y,next;ll d;}a[510000];int len,last[210000];
void ins(int x,int y,ll d) {len++;a[len].x=x;a[len].y=y;a[len].d=d;a[len].next=last[x];last[x]=len;}
int G,fa[210000],bian[210000];ll D;
void dfs(int x,ll d,int f) {
if(D<d) {D=d;G=x;}
for(int k=last[x];k;k=a[k].next) {
int y=a[k].y;
if(y!=f){fa[y]=x;bian[y]=k;dfs(y,d+a[k].d,x);}
}
}
int s[210000];
ll T;bool v[210000];
void dfs1(int x,ll d,int f) {
if(T<d)T=d;
for(int k=last[x];k;k=a[k].next) {
int y=a[k].y;
if(v[y]==true&&y!=f) dfs1(y,d+a[k].d,x);
}
}
int ans;
void dfs2(int x,int d,int f,int ed) {
if(x==ed){ans=d;return ;}
for(int k=last[x];k;k=a[k].next) {
int y=a[k].y;
if(y!=f) dfs2(y,d+1,x,ed);
}
}
int main() {
int n;scanf("%d",&n);len=0;memset(last,0,sizeof(last));
for(int i=1;i<n;i++) {
int x,y;ll d;scanf("%d%d%lld",&x,&y,&d);
ins(x,y,d);ins(y,x,d);
}
int X,Y;
memset(bian,0,sizeof(bian));dfs(1,0,0);X=G;D=0;dfs(X,0,0);Y=G;
int x=Y,slen=0;memset(v,true,sizeof(v));
while(x!=X) {s[++slen]=x;v[x]=false;x=fa[x];}
s[++slen]=X;v[X]=false;
int ansx=Y;ll K=a[bian[s[1]]].d;
for(int i=2;i<=slen;i++) {
T=0;dfs1(s[i],0,0);
if(T==K)ansx=s[i];K+=a[bian[s[i]]].d;
}
for(int i=slen;i>=2;i--) bian[s[i]]=bian[s[i-1]];bian[s[1]]=0;
int ansy=X;K=a[bian[s[slen]]].d;
for(int i=slen-1;i>=1;i--) {
T=0;dfs1(s[i],0,0);
if(T==K)ansy=s[i];K+=a[bian[s[i]]].d;
}dfs2(ansx,0,0,ansy);printf("%lld\n%d\n",D,ans);
return 0;
}``````

https://chowdera.com/2020/12/20201207142535674l.html