bzoj千题计划134：bzoj3124: [Sdoi2013]直径

http://www.lydsy.com/JudgeOnline/problem.php?id=3124

第一问：

dfs1、dfs2

dfs2中记录dis[i]表示点i距离最长链左端点的距离

第二问：

所有直径的交集一定是最长链上连续的一段

dfs3记录最长链，

从最长链上每个点i开始dfs4，记录能到达的非最长链点的最远距离mx

如果mx==最长链-dis[i]，更新交集的左端点

如果mx==dis[i]，找到交集的右端点，退出

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long LL;

#define N 200001

int tot;

int front[N],nxt[N<<],to[N<<],val[N<<];

LL mx,max_len;

int wh;

LL dis[N]; 

int path[N],num;

bool use[N];

int cf[N];

void read(int &x)

{

    x=; char c=getchar();

    while(!isdigit(c))  c=getchar();

    while(isdigit(c)) { x=x*+c-''; c=getchar();  }

}

void add(int u,int v,int w)

{

    to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; val[tot]=w;

    to[++tot]=u; nxt[tot]=front[v]; front[v]=tot; val[tot]=w;

}

void dfs1(int x,int y,LL d)

{

    if(d>mx) mx=d,wh=x;

    for(int i=front[x];i;i=nxt[i])

    {

        if(to[i]==y) continue;

        dfs1(to[i],x,d+val[i]);

    }

}

void dfs2(int x,int y,LL d)

{

    dis[x]=d;

    if(d>max_len) max_len=d,wh=x;

    for(int i=front[x];i;i=nxt[i])

    {

        if(to[i]==y) continue;

        dfs2(to[i],x,d+val[i]);

    }

}

void dfs3(int x,LL d)

{

    path[++num]=x;

    use[x]=true;

    for(int i=front[x];i;i=nxt[i])

    {

        if(dis[to[i]]==d-val[i]) dfs3(to[i],d-val[i]);

    }

}

void dfs4(int x,int y,LL d)

{

    mx=max(mx,d);

    for(int i=front[x];i;i=nxt[i])

    {

        if(to[i]==y || use[to[i]]) continue;

        dfs4(to[i],x,d+val[i]);

    }

}

int main()

{

    int n;

    read(n);

    int u,v,w;

    for(int i=;i<n;++i)

    {

        read(u); read(v); read(w);

        add(u,v,w);

    }

    dfs1(,,);

    dfs2(wh,,);

    cout<<max_len<<'\n';

    dfs3(wh,max_len);

    int L=,R=num;

    for(int i=;i<num;++i)

    {

        mx=;

        dfs4(path[i],,);

        if(mx==max_len-dis[path[i]]) L=i;

        if(mx==dis[path[i]]) { R=i; break; }

    }

    cout<<R-L;

}

3124: [Sdoi2013]直径

Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 1261 Solved: 603
[Submit][Status][Discuss]

Description

小Q最近学习了一些图论知识。根据课本，有如下定义。树：无回路且连通的无向图，每条边都有正整数的权值来表示其长度。如果一棵树有N个节点，可以证明其有且仅有N-1 条边。路径：一棵树上，任意两个节点之间最多有一条简单路径。我们用 dis(a,b)
表示点a和点b的路径上各边长度之和。称dis(a,b)为a、b两个节点间的距离。
直径：一棵树上，最长的路径为树的直径。树的直径可能不是唯一的。
现在小Q想知道，对于给定的一棵树，其直径的长度是多少，以及有多少条边满足所有的直径都经过该边。

Input

第一行包含一个整数N，表示节点数。
接下来N-1行，每行三个整数a, b, c ，表示点 a和点b之间有一条长度为c
的无向边。

Output

共两行。第一行一个整数，表示直径的长度。第二行一个整数，表示被所有
直径经过的边的数量。

Sample Input

6
3 1 1000
1 4 10
4 2 100
4 5 50
4 6 100

Sample Output

1110
2

【样例说明】
直径共有两条，3 到2的路径和3到6的路径。这两条直径都经过边(3, 1)和边(1, 4)。

HINT

对于100%的测试数据：2≤N≤200000，所有点的编号都在1..N的范围内，

边的权值≤10^9。

秒客网