# P3304 [SDOI2013]直径 题解

## 评论

• 荔枝君
惧聚聚聚聚聚聚聚聚%%%%%%
• 荔枝君
%%%%%%%%%
• 我不认识你
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
• AllanGong
TQLTQL%%%ORZORZ
• 我不认识你
太~强~了！~
• 我是蒟弱
什么orz，什么%%%，都不够
• 我是蒟弱
大~丶~弓~虽~了~！
• 我是蒟弱
用一个个 一、丨、丿、丶写出绝妙题解！
• 我是蒟弱
Good solution!
• yangyucheng66
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

#include <stdio.h>
#include <queue>
using namespace std;
int const N=4e5+1;
struct node{
int x;
long long val;
friend bool operator <(node a, node b){
return a.val<b.val;
}
};
int n,tot,to[N],pre[N],last[N],fa[N],ans=0;
long long v[N],d[N],f[N];
priority_queue<node> h;
void add(int a, int b, int c){
to[++tot]=b;
pre[tot]=last[a];
last[a]=tot;
v[tot]=c;
}
void dfs(int x, int father, long long deep){
d[x]=deep;
fa[x]=father;
f[x]=0;
for (int i=last[x];i;i=pre[i])
if (to[i]!=father) {
dfs(to[i],x,d[x]+v[i]);
f[x]=max(f[x],f[to[i]]+v[i]);
}
}
void work(int x, int father, int deep){
dfs(x,father,deep);
while (true){
int y=0,cnt=0;
for (int i=last[x];i;i=pre[i])
if (to[i]!=father && f[x]==f[to[i]]+v[i]) y=to[i],cnt++;
if (cnt==0 || cnt>=2) break;
father=x;
x=y;
ans++;
}
}
int main(){
freopen("p3304.in","r",stdin);
scanf("%d",&n);
if (n==2){
printf("1");
return 0;
}
for (int i=1;i<=n-1;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
}
dfs(1,0,0);
int now=0;
for (int i=1;i<=n;i++)
if (d[i]>d[now]) now=i;
dfs(now,0,0);
now=0;
for (int i=1;i<=n;i++)
if (d[i]>d[now]) now=i;
long long L=d[now];
while (d[fa[now]]*2>=L) now=fa[now];
if (d[now]*2==L){
dfs(now,0,0);
for (int i=last[now];i;i=pre[i])
h.push((node){to[i],v[i]+f[to[i]]});
node a=h.top();
h.pop();
node b=h.top();
h.pop();
if (h.empty()){
ans+=2;
work(a.x,now,0);
work(b.x,now,0);
} else{
node c=h.top();
if (b.val>c.val){
ans+=2;
work(a.x,now,0);
work(b.x,now,0);
} else{
if (a.val>b.val){
ans++;
work(a.x,now,0);
}
}
}
}
else{
ans++;
work(now,fa[now],0);
work(fa[now],now,0);
}
printf("%lld\n",L);
printf("%d\n",ans);
return 0;
} 

## 评论

• Ureka_Gestalt
多谢大佬写得通俗易懂%%%
• ｃｈｉｌｌ
noob
• M_sea
唯一一篇看懂的题解（逃
• 1517460958dyc
您的变量命名再改改就更通俗易懂了（逃
• Zekrom
JU(逃

ls[i]表示这个点到直径左端点的距离。

rs[i]表示这个点到直径右端点的距离。（左右随意定）

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
vector<int> a[200001],b[200001];
int last[200001],u,v,next[200001];
long long dis[200001],mmm[200001],op;
bool vv[200001];
void dfs1(int o,long long p,int q)
{
if(p>op){op=p;u=o;}
for(int i=0;i<a[o].size();i++)
if((!vv[a[o][i]])&&(a[o][i]!=q))
{
vv[a[o][i]]=true;
dfs1(a[o][i],p+b[o][i],o);
}
}
void dfs2(int o,long long p,int q)
{
last[o]=q;
dis[o]=p;
if(p>op){op=p;v=o;}
for(int i=0;i<a[o].size();i++)
if((!vv[a[o][i]])&&(a[o][i]!=q))
{
vv[a[o][i]]=true;
dfs2(a[o][i],p+b[o][i],o);
}
}
int main()
{
int n;
cin>>n;
for(int i=1;i<n;i++)
{
int x,y,z;
cin>>x>>y>>z;
a[x].push_back(y);
b[x].push_back(z);
a[y].push_back(x);
b[y].push_back(z);
}
memset(vv,0,sizeof(vv));op=0;
dfs1(1,0,0);
memset(vv,0,sizeof(vv));op=0;
dfs2(u,0,0);
int distance=dis[v];
cout<<dis[v]<<endl;
memset(vv,0,sizeof(vv));
for(int i=v;i!=0;i=last[i]) vv[i]=true;
for(int i=v;i!=0;i=last[i])
{
op=0;
dfs1(i,0,0);
mmm[i]=op;
}
int j=v;
for(int i=last[v];i!=0;i=last[i]) next[i]=j,j=i;
int ans=0;
int i;
for(i=j;i!=0;i=next[i])
if(dis[v]-dis[i]==mmm[i]) break;
for(;i!=0;i=last[i])
{
if(dis[i]==mmm[i]) break;
ans++;
}
cout<<ans<<endl;
return 0;
}

## 评论

• Ureka_Gestalt
AC的花233
• 汪锦程
图片有严重错误，直径的端点只有一条边与其相连。图中最上面那个点肯定不是直径端点。
• GoldenPotato137
@_J_C_ 我在用您的程序对拍的时候拍出一组hack数据： 2 2 1 10 输出显然是1 但是您的输出为0

[悄咪咪的给题解加标签:树型结构，bfs，dfs，链表]

T.T想了快一天了，最后瞄了一眼题解，重构之后写出来了QwQ

[楼下有一位大佬题解详尽而且很通俗易懂，不过他大概是忘了给代码加注释了……我主要分享一下具体实现]

### [系统提示:]恭喜你，思路到此结束。如果你对如何实现有困惑，不妨继续往下阅读。

#include <cstdio>
#include <cstdlib>

#include <queue>

#define FOR_EDGE(i, pt) for (int i(iHead[pt]); i; i = all[i].next)//这个宏用来枚举这个点连出去的所有边

class edge
{
public:
int fr, to, next;
long long len;
}all[412345];

int iEnd(2);

void add(int fr, int to, long long len)//加边
{
all[iEnd].fr = fr;
all[iEnd].to = to;
all[iEnd].len = len;
}

int n;

int left, right;//第一条直径的左右端（理解上可以是左右，实际上鬼知道呢2333）
int NextVis;
int bVis[212345], forward[212345];
long long disforward[212345];
long long dis[212345];

void bfs(int start, int& faraway)//寻找距离start最远的点faraway
{
faraway = 0;
dis[start] = 0;
bVis[start] = ++NextVis;
std::queue<int> que;
que.push(start);
while (!que.empty())
{
int now(que.front());
que.pop();
FOR_EDGE(i, now)
{
if (bVis[all[i].to] ^ NextVis)//不要多虑，就是"!="的意思
{
bVis[all[i].to] = NextVis;
dis[all[i].to] = dis[now] + all[i].len;
forward[all[i].to] = now;//链表记录这个点来处
disforward[all[i].to] = all[i].len;
que.push(all[i].to);
if (dis[all[i].to] > dis[faraway]) faraway = all[i].to;
}
}
}
}

int mid[212345], end;//直径端点间的点
bool bInList[212345];
long long leftlen[212345], rightlen[212345];//这个点到直径左/右端的距离，用它在mid中的下标访问
long long length[212345];//这个点向两侧延伸的最大长度，用点的标号访问（比较人家dfs还要用）

int dfs(int now)
{
FOR_EDGE(i, now)
{
if (!bInList[all[i].to] && bVis[all[i].to] ^ NextVis)//这个点不在直径内 且 这个点未被访问
{
bVis[all[i].to] = NextVis;
long long val(all[i].len + dfs(all[i].to));//
if (val > length[now]) length[now] = val;
}
}
return length[now];
}

inline int max(int a, int b) { return a > b ? a : b; }

int main()
{
scanf("%d", &n);
for (int i(1); i != n; ++i)
{
int fr, to;
long long len;
scanf("%d%d%lld", &fr, &to, &len);
}
left = 1;
bfs(left, right);//两次bfs得到直径
bfs(right, left);
long long ans(dis[left]);
int pos(left), disleft(0), disright(dis[left]);//由于pos从左端点开始，它最初到右端距离即左端点到右端点的距离dis[left]
bInList[left] = true;
bInList[right] = true;//左右端点当然在直径里啦
while (pos != right)//这里pos开始从left向right（从"左"到"右"）
{
leftlen[end] = disleft += disforward[pos];//累加它到左端的距离
rightlen[end] = disright -= disforward[pos];
pos = forward[pos];
mid[end] = pos;
bInList[pos] = true;
++end;
}
int leftend(0), rightend(end - 1);
for (int i(0); i != end; ++i)
{
++NextVis; dfs(mid[i]);
if (length[mid[i]] == leftlen[i]) leftend = i;
if (length[mid[i]] == rightlen[i])
{
rightend = i;//如果右边分叉掉了，在向右枚举i就没有必要了：因为右边都可以扔了
break;
}
}
printf("%lld\n%d\n", ans, max(0, rightend - leftend));
return 0;
}
//The newline at the end of file :)

• 顾月
tql.!
• COUPDETAT
%%%
• COUPDETAT
1551看不懂
• 姝雨墨
垃圾！

# 【luogu-3304】【SDOI2013】直径

## 前提

• 树的直径会有很多条
• 一般地，树的这些直径有且只有一段重合。特殊地，这一段可能是一个点。 如图路径$3-1-4$是重合的。

## 思路

求出重合的这一段的长度，就是最终答案。

## 求法

要求这条路径的长度，由于是在树上的，所以只需要求出路径两端的端点即可

## 代码

/*!
* FileName: luogu-3304.cpp
* This Problem is on luogu. The ID of the problem is 3304.
* Luogu: https://www.luogu.org/space/show?uid=44615
* Github: https://github.com/oldsuold/
* Gitee: https://gitee.com/Shu_Yu_Mo/
* These words were created by an amazing tool written by Shu_Yu_Mo.
*/
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstring>
#include<iostream>
#include<cmath>
#include<vector>
#include<queue>
#include<algorithm>
#define inf 0x7fffffff
#define int long long
using namespace std;
const int _N = 200100;
const int _M = _N;
{
char c = getchar(); int sign = 1; int x = 0;
while(c > '9' || c < '0') { if(c=='-')sign = -1; c = getchar(); }
while(c <= '9' && c >= '0') { x *= 10; x += c - '0'; c = getchar(); }
return x * sign;
}
void swap(int & x, int & y)
{
int t = x;
x = y;
y = t;
}
int n, m;
struct edges{
int node;
int w;
int nxt;
}edge[_M << 1];
int tot = 0;
void add(int u, int v, int w)
{
edge[tot].node = v;
edge[tot].w = w;
}
bool vis[_N];
int dist[_N];
void dfs(int nowNode)
{
//  if(vis[edge[i].node]) continue;
vis[nowNode] = true;
for(register int i = head[nowNode];i;i = edge[i].nxt)
{
if(vis[edge[i].node]) continue;
dist[edge[i].node] = dist[nowNode] +  edge[i].w;
dfs(edge[i].node);
}
}
bool B[_N];
int Er[_N << 1], tot_Er = 0;
int first[_N], tot_F = 0;
int MinId = inf;
int MaxId = -inf;
void dfsForLCA(int k)
{
vis[k] = true;
first[k] = ++tot_F;
Er[++tot_Er] = k;
for(register int i = head[k];i;i = edge[i].nxt)
{
int SonNode = edge[i].node;
if(vis[SonNode]) continue;
dfsForLCA(SonNode);
Er[++tot_Er] = k;
}
}
int To;//, ansB;
int ans = 0;
int RunningAns = 0;
void dfsLast(int k)
{
if(k == To)
{
ans = RunningAns;
return;
}
vis[k] = true;
for(register int i = head[k];i;i = edge[i].nxt)
{
int SonNode = edge[i].node;
if(vis[SonNode]) continue;
RunningAns++;
dfsLast(SonNode);
RunningAns--;
}
}
signed main()
{
//  freopen("test.in.txt", "r", stdin);
int k = 1;
memset(vis, false, sizeof(vis));
n = read(), m = n - 1;
for(register int i = 1;i <= m;i++)
{
k = tmpx;
}
int MaxDis = 0, MaxId;
memset(dist, 0, sizeof(dist));
//  printf("Start at %d\n", k);
dfs(k);
for(register int i = 1;i <= n;i++)
{
//      printf("%d ", dist[i]);
if(dist[i] > MaxDis)
{
MaxDis = dist[i];
MaxId = i;
}
}
//  printf("%d\n", MaxId);

memset(dist, 0, sizeof(dist));
memset(vis, false, sizeof(vis));
dfs(MaxId);
int MaxDis_ = 0;
int MaxAns = -inf;
for(register int i = 1;i <= n;i++)
MaxDis_ = max(MaxDis_, dist[i]);
MaxAns = MaxDis_;
for(register int i = 1;i <= n;i++)
B[i] = (dist[i] == MaxDis_);

memset(first, -1, sizeof(first));
memset(vis, false, sizeof(vis));
dfsForLCA(MaxId);

for(register int i = 1;i <= tot_Er;i++)
{
//      printf("%d ", Er[i]);
if(B[Er[i]])
{
MinId = min(MinId, i);
MaxId = max(MaxId, i);
}
}//cout<<endl;
//  for(register int i = 1;i <= tot_Er;i++)
//      printf("%d ", first[Er[i]]);
//printf("\n%d %d\n", MinId, MaxId);
int F_Min = inf;
int LCA_Id;
for(register int i = MinId;i <= MaxId;i ++)
{
//printf("at %d , Er[%d] = %d, First[%d] = %d\n", i, i, Er[i], Er[i], first[Er[i]]);
if(F_Min > first[Er[i]])
{
F_Min = first[Er[i]];
LCA_Id = Er[i];
}
}
//printf("LCA = %d\n", LCA_Id);
//  printf("MaxDist = %d, node = %d ,%d\n", MaxDis2, MaxId2, MaxId);

memset(dist, 0, sizeof(dist));
memset(vis, false, sizeof(vis));
int S = Er[MinId];
dfs(S);//printf("%d", S);
memset(first, -1, sizeof(first));
tot_Er = 0;
tot_F = 0;
for(register int i = 1;i <= n;i++)
B[i] = (dist[i] == MaxDis_);
memset(vis, false, sizeof(vis));
dfsForLCA(S);
MinId = inf; MaxId = -inf;//cout<<endl<<endl<<"&"<<endl;
for(register int i = 1;i <= tot_Er;i++)
{
//      printf("%d ", Er[i]);
if(B[Er[i]])
{
MinId = min(MinId, i);
MaxId = max(MaxId, i);
}
}
//  printf("MaxId = %d, MinId = %d\n", MaxId, MinId);
F_Min = inf;
int LCA_Id2;
for(register int i = MinId;i <= MaxId;i ++)
{
//      printf("at %d , Er[%d] = %d, First[%d] = %d\n", i, i, Er[i], Er[i], first[Er[i]]);
if(F_Min > first[Er[i]])
{
F_Min = first[Er[i]];
LCA_Id2 = Er[i];
}
}
//  printf("\n###%d %d\n", LCA_Id2, LCA_Id);
To = LCA_Id;
memset(vis, false, sizeof(vis));
dfsLast(LCA_Id2);
printf("%lld\n%lld", MaxAns, ans);

return 0;
}


## 评论

• speaker
太复杂
• GKxx
写得很清楚！赞一个！
• GKxx
有一个小地方可能写错了？最后答案不是δ(x, y)，而是x到y的边数

### 题解

• 当 $y$ 到达的最远结点 $z$ 横穿$\delta(u,v)$时，记与之相交的结点为 $x$。此时有$\delta(y,z)=\delta(y,x)+\delta(x,z)$。而此时$\delta(y,z)>\delta(y,v)$，故可得$\delta(x,z)>\delta(x,v)$。由$1$的结论可知该假设不成立。

• 当 $y$ 到达的最远结点 $z$ 与$\delta(u,v)$不相交时，记 $y$ 到 $v$ 的最短路首先与$\delta(u,v)$相交的结点是 $x$。由假设$\delta(y,z)>\delta(y,x)+\delta(x,v)$。而$\delta(y,z)+\delta(y,x)+\delta(x,u)$又可以形成$\delta(z,u)$，而$\delta(z,u)>\delta(x,u)+\delta(x,v)+2\delta(y,x)=\delta(u,v)+2\delta(y,x)$矛盾。

• -

### 代码

#include <cstdio>
#include <cstring>
#include <vector>
#include <cctype>
#include <algorithm>
#define ll long long
using namespace std;

namespace fast_io {//快速输入模板
static const int IN_LEN=1000000;static char buf[IN_LEN],*s,*t;
}
static bool iosig;static char c;
if(c=='-')iosig=true;if(c==-1)return;
}
x=((x+(x<<2))<<1)+(c^'0');
if(iosig)x=-x;
}
}using namespace fast_io;

const int MAXN = 300000;
struct Edge{
int from,to,len;
};
int n,u=0,v=0,fa[MAXN];
ll dis[MAXN],ans1,ans2;
vector<Edge> edge[MAXN];
edge[a].push_back((Edge){a,b,c});
edge[b].push_back((Edge){b,a,c});
}

void init(){
int a,b,c;
for(int i = 1;i<=n-1;i++){
}
}

void dfs(int nown,int f){//寻找从nown节点出发的最长路
fa[nown] = f;
for(int i = 0;i<edge[nown].size();i++){
Edge e = edge[nown][i];
if(e.to == f) continue;
dis[e.to] = dis[nown] + e.len;
dfs(e.to,nown);
}
}

void find(){
memset(dis,0,sizeof(dis));
dfs(1,0);
for(int i = 1;i<=n;i++)//第一次搜到的节点记作直径的一个端点u
if(dis[i] > dis[u])
u = i;
memset(dis,0,sizeof(dis));
dfs(u,0);
for(int i = 1;i<=n;i++)//第二次搜到的节点记作直径的另一个端点v
if(dis[i] > dis[v])
v = i;
}

bool dfs2(int nown,ll len){//dfs寻找是否从某个节点存在长度为len的路径
if(len == 0) return true;
for(int i = 0;i < edge[nown].size();i++){
Edge e = edge[nown][i];
if(e.to == fa[nown]) continue;
if(dfs2(e.to,len - e.len))
return true;
}
return false;
}

void solve(){
static int nex[MAXN];
int t = v,tmp = 0;//tmp为直径长度
while(t!=u){//记录从u到v的路径
nex[fa[t]] = t;
t = fa[t];
tmp++;
}
//l代表到右节点最近的满足上文性质的点，r代表到左节点最近的满足上文性质的点
int l = 0,r = tmp,nowt = 0;
//循环中dis[t] = d(u,t)
for(t = u;t!=v;t = nex[t]){
for(int i = 0;i<edge[t].size();i++){
Edge e = edge[t][i];
if(e.to == fa[t] || e.to == nex[t]) continue;
if(dfs2(e.to,dis[t] - e.len))
l = max(nowt,l);//寻找离u最远的t,满足d(u',t) = d(u,t),得到即为x,名字叫做l
else if(dfs2(e.to,(dis[v] - dis[t])- e.len))
r = min(r,nowt);//寻找离v最远的t,满足d(t,v') = d(t,v),得到即为y,名字叫做r
}
nowt++;
}
ans1 = dis[v];//直径长度
ans2 = r - l;//在这里事实上是求了r和l的位置并求出ans2
}

int main(){
init();
find();
solve();
printf("%lld\n%lld\n",ans1,ans2);
return 0;
}