P3304 [SDOI2013]直径 题解


以下题解仅供学习参考使用。

抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在洛谷是严格禁止的。

洛谷非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看洛谷社区规则

评论

  • speaker
    太复杂
  • GKxx
    写得很清楚!赞一个!
  • GKxx
    有一个小地方可能写错了?最后答案不是δ(x, y),而是x到y的边数
作者: cqqqwq 更新时间: 2018-05-12 20:59  在Ta的博客查看 举报    6  

题意

定义一棵树上最长的路径为树的直径。树的直径可能不唯一。

给定的一棵$n$个结点的树,求其直径的长度,以及有多少条边满足所有的直径都经过该边。

Blog

同步于:Chen's Blog

题解

很有趣的一道题。

首先找直径。先从任取点$t$出发,到达最远的一个点$u$。再从$u$出发,到达最远的点$v$,$u$,$v$之间的路径即为树的直径。

这比较显然。

令$\delta (u,v)$为$u,v$两点间路径,其数值即为路径长度。

引理:在一棵树中,$x$、$y$ 和 $z$ 是三个不同的结点。当 $x$ 到 $y$ 的最短路与 $y$ 到 $z$ 的最短路不重合时,$x$ 到 $z$ 的最短路就是这两条最短路的拼接。

定理1:在一棵树中,以任意结点出发所能到达的最远结点,一定是该树直径的端点之一。

证明:假设这条直径是$\delta (u,v)$。分两种情况:

当出发结点 $y$ 在$\delta(u,v)$上时,假设到达的最远结点 $z$ 不是 $u,v$ 中的任一个。这时将$\delta(y,z)$与不与之重合的$\delta(y,u)$拼接(也可以假设不与之重合的是直径的另一个方向),可以得到一条更长的路径,矛盾。

当出发结点 $y$ 不在$\delta(u,v)$上时,分两种情况:

  • 当 $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)$矛盾。

    • -

先求出了直径,我们就发现一件好玩的事情。

定理2:对于一个边权为正数的树,其所有的直径必然两两有交点。

证明:设树的一条直径为$\delta (u,v)$,任取另一直径为$\delta (u',v')$。其长度设为$d$。

若两直径有公共部分,显然有公共点。

若没有公共部分,则必有一条路径$\delta (x,y)$连接两条直径,$x$在$\delta (u,v)$上,$y$在$\delta (u',v')$上。

在$\delta(u,x)$和$\delta(x,v)$中,不妨设$\delta(u,x) \geq \frac{1}{2} \times d$。同理设$\delta(u',y) \geq \frac{1}{2} \times d$,又因为$\delta (x,y) > 0$,所以$\delta (u,u') = \delta(u,x) + \delta(x,y) + \delta(y,u') > d = \delta(u,v)$,矛盾。


我们要求的是有多少个边在在所有的直径上。我们已经求得了一条直径$\delta(u,v)$。

令$x$为在$\delta(u,v)$上离$u$点最远的点,满足存在点$u'$,使得$\delta(x,u') = \delta(x,u)$,且$u \neq u'$,则可得$\delta(u',v)$也是一条直径。

同理$y$为在$\delta(u,v)$上离$v$点最远的点,满足存在点$v'$,使得$\delta(x,v') = \delta(x,v)$,且$v \neq v'$,则可得$\delta(u,v')$也是一条直径。

这两个东西都可以在找出直径之后一边扫直径一边$dfs$出来。这个时候我们注意到,$x$应当在$y$左侧,且$x$在直径左半部,$y$在直径右半部,排列顺序大概是这个样子$u\leftrightarrow x \leftrightarrow y \leftrightarrow v$。很容易看出,$x$与$y$之间的部分,就是所有直径的公共边。答案即为$\delta(x,y)$。

时间复杂度大约是一个常数比较大的$O(n)$。

代码

懒得写bfs,于是就比较的慢...

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

namespace fast_io {//快速输入模板
    inline char read(){
        static const int IN_LEN=1000000;static char buf[IN_LEN],*s,*t;
        return s==t?(((t=(s=buf)+fread(buf,1,IN_LEN,stdin))==s)?-1:*s++) : *s++;
    }
    inline void read(int &x){
        static bool iosig;static char c;
        for (iosig=false,c=read();!isdigit(c);c=read()){
            if(c=='-')iosig=true;if(c==-1)return;
        }
        for(x=0;isdigit(c);c=read())
            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];
void addedge(int a,int b,int c){
    edge[a].push_back((Edge){a,b,c});
    edge[b].push_back((Edge){b,a,c});
}

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

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;   
}

评论

  • _HZY_
    ORZ 这是我唯一看懂的题解, 我果然太弱了。。。
作者: ljc20020730 更新时间: 2019-07-24 14:14  在Ta的博客查看 举报    2  

先将树的任意一条直径找出来,考虑树的直径一定是交于一条线段上的。 那么从直径两段往中间搜一定是中间这一段路径是唯一的。

设直径是$[s,t]$,把这个直径拉出来,左侧是$s$,右侧是$t$;

  • 先以$s$为根,然后跑整一棵树,求出子树最长链和它的条数.
  • 从$t$开始向左遍历整个直径,找到最左侧的一个点$v$使得其右侧相邻的一条边不是必经边(即使得当前点的右侧最长链条数不发生变化)
  • 然后以$t$为根,然后跑整一棵树,求出子树最长链和它的条数.
  • 从$s$开始向右遍历整个直径,找到最右侧的一个点$u$使得其左侧相邻的一条边不是必经边(即使得当前点的左侧最长链条数不发生变化)
  • 链$[u,v]$中所有的边都是必经边。

上述过程显然是一个线性过程,复杂度是$O(n)$

# include <cstdio>
# include <iostream>
# include <cstring>
# define int long long
using namespace std;
const int N=2e5+10;
struct rec{ int pre,to,w;}a[N<<1];
int n,tot;
int d[N],head[N],tim[N],f[N],path[N],pre[N];
void adde(int u,int v,int w)
{
    a[++tot].pre=head[u];
    a[tot].to=v;
    a[tot].w=w;
    head[u]=tot;
}
void dfs1(int u,int fa,int L)
{
    d[u]=L;
    for (int i=head[u];i;i=a[i].pre) {
        int v=a[i].to; if (v==fa) continue;
        dfs1(v,u,L+a[i].w);
    }
}
void dfs2(int u,int fa,int L)
{
    d[u]=L;
    for (int i=head[u];i;i=a[i].pre) {
        int v=a[i].to; if (v==fa) continue;
        pre[v]=u; dfs2(v,u,L+a[i].w);
    }
}
void dfs3(int u,int fa)
{
    int cnt=0,mx=0; bool leaf=1;
    for (int i=head[u];i;i=a[i].pre) {
        int v=a[i].to; if (v==fa) continue; leaf=0;
        dfs3(v,u);
        if (f[v]+a[i].w>mx) mx=f[v]+a[i].w,cnt=tim[v];
        else if (f[v]+a[i].w==mx) cnt+=tim[v];
    }
    if (leaf) f[u]=0,tim[u]=1;
    else f[u]=mx,tim[u]=cnt;
}
signed main()
{
    scanf("%lld",&n);
    for (int i=1;i<n;i++) {
        int u,v,w; scanf("%lld%lld%lld",&u,&v,&w);
        adde(u,v,w); adde(v,u,w);
    }
    memset(d,0,sizeof(d));
    dfs1(1,0,0); int s=0;
    for (int i=1;i<=n;i++) if (d[i]>d[s]) s=i;
    memset(d,0,sizeof(d));
    dfs2(s,0,0); int t=0; pre[s]=-1;
    for (int i=1;i<=n;i++) if (d[i]>d[t]) t=i;
    printf("%lld\n",d[t]);
    int u=t,v; while (pre[u]!=-1) path[++path[0]]=u,u=pre[u]; path[++path[0]]=u;
    for (int i=1;i<=path[0]/2;i++) swap(path[i],path[path[0]-i+1]);
    memset(f,0,sizeof(f)); memset(tim,0,sizeof(tim)); dfs3(s,0);
    v=path[0];
    for (int i=path[0]-1;i>=1;i--)
     if (tim[path[i]]-tim[path[i+1]]>0) v=i;
    memset(f,0,sizeof(f)); memset(tim,0,sizeof(tim)); dfs3(t,0);
    u=1;
    for (int i=2;i<=path[0];i++)
     if (tim[path[i]]-tim[path[i-1]]>0) u=i;
    printf("%lld\n",v-u);
    return 0;
}

评论

  • 还没有评论
作者: Toheart 更新时间: 2017-08-28 22:15  在Ta的博客查看 举报    3  

洛谷首题解!

第一问:裸求树的直径,跑两遍DFS/DFS/树形DP,原理请百度。

第二问:易知答案边一定在开始求的直径上,易知将所有的直径覆盖在一起形似一个两边有分叉的树干,所以要缩小左右端点的范围。具体要遍历直径,并判断每个点是否为两直径交点,若是则将分叉的点舍弃掉。

···

#include<bits/stdc++.h>
using namespace std;
const int maxn = 200010;
int n, tot, far;
long long maxd;
int st[maxn], fa[maxn];
long long dis[maxn];
bool isol[maxn];
struct node{
    int v, w, nxt;
} edge[2*maxn];
inline void in(int x, int y, int z){
    edge[++tot].v = y;
    edge[tot].w = z;
    edge[tot].nxt = st[x];
    st[x] = tot; 
}
void DFS(int now, int f){
    fa[now] = f;
    if(maxd < dis[now]){
        far = now;
        maxd = dis[now];
    }
    for(int i = st[now]; i; i = edge[i].nxt){
        int to = edge[i].v;
        if(to != f){
            dis[to] = dis[now] + edge[i].w;
            DFS(to, now);
        }
    }
}
void Liuhaoyu(int now, int f){
    if(maxd < dis[now])    maxd = dis[now];
    for(int i = st[now]; i; i = edge[i].nxt){
        int to = edge[i].v;
        if(to != f && !isol[to]){
            dis[to] = dis[now] + edge[i].w;
            Liuhaoyu(to, now);
        }
    }
}
int main(){
    scanf("%d", &n);
    for(int i = 1, x, y, z; i < n; i++){
        scanf("%d%d%d", &x, &y, &z);
        in(x, y, z);
        in(y, x, z);
    }
    DFS(1, 0);
    //printf("%d\n", far);
    int op = far;
    maxd = dis[op] = 0;
    //memset(fa, 0, sizeof(fa));
    DFS(op, 0);
    //printf("%d\n", far);
    /*for(int i = 1; i <= n; i++)
        printf("%d ", dis[i]);*/
    printf("%lld\n", maxd);
    for(int i = far; i; i = fa[i])
        isol[i] = 1;
    int l = op, r = far;
    bool flag = 0;
    for(int i = fa[far]; i != op; i = fa[i]){
        int ld = dis[i];
        int rd = dis[far] - dis[i];
        maxd = dis[i] = 0;
        Liuhaoyu(i, 0);
        if(maxd == ld && !flag){
            l = i;
            flag = 1;

}//左端点只能缩一次,因为点从右端遍历过来,若再改变左端点范围会扩大。

        if(maxd == rd)    r = i;
    }
    long long ans = 0;
    for(int i = r; i != l; i = fa[i])//注意是边,所以少一个 
        ans++;
    printf("%lld\n", ans);
    return 0;
}
···

评论

  • 还没有评论
作者: Hock 更新时间: 2019-10-28 18:41  在Ta的博客查看 举报    1  

来写一份题解吧 这好像是近期我的第一篇题解

首先这道题目需要了解树的直径的一个性质

数的直径必须经过一个点 且这个点为这个直径的中点

反证法:

假设有两条不相交的直径

因为树上任意两点都有一条唯一的路径

那么假设连接两个中点的长度为len, 直径长度为max_d

那么两条直径的两端距离为max_d + len > max_d

那么直径长度不是len

矛盾

所以两条直径必须经过一个点

同理证明这个点是中点 也可以用相同方法 易证

那么有了这个的话 做这道题应该好做多了 先两遍$dfs$跑出$l$$和r$

然后对于两个端点所经过的路径上 跑一遍$dfs$ 如果$maxd == dis$那么就说明那个点不是必须点 可以$pass$ 然后就可以了

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <set>
#include <map>
#include <queue>

using namespace std;

typedef long long ll;

const int INF = 2139062143;

#define DEBUG(x) std::cerr << #x << " = " << x << std::endl

inline ll read() {
    ll f = 1, x = 0;char ch;
    do {ch = getchar();if (ch == '-')f = -1;} while (ch > '9' || ch < '0');
    do {x = x * 10 + ch - '0';ch = getchar();} while (ch >= '0' && ch <= '9');
    return f * x;
}

const int MAX_N = 2e5 + 7;

struct EDGE {
    int to, next, w;
} edge[MAX_N << 1];

int head[MAX_N], E;

void addedge (int u, int v, int w) {
    edge[++E].to = v;
    edge[E].next = head[u];
    edge[E].w = w;
    head[u] = E;
}

int n, ans, f[MAX_N], vis[MAX_N], p, l, r;

ll dep[MAX_N], max_d;

inline void dfs (int u, int fa) {
    f[u] = fa;
    for (int i = head[u]; i; i = edge[i].next ) {
        int v = edge[i].to, w = edge[i].w;
        if (v == fa) continue;
        dep[v] = dep[u] + w;
        if (dep[v] > max_d) {
            max_d = dep[v];
            p = v;
        }
        dfs (v, u);
    }
}

inline void dfs2 (int u, int fa) {
    for (int i = head[u]; i; i = edge[i].next ) {
        int v = edge[i].to, w = edge[i].w;
        if (vis[v] || fa == v) continue;
        dep[v] = dep[u] + w;
        if (dep[v] > max_d) max_d = dep[v];
        dfs2 (v, u);
    }
}

int main() {
    n = read ();
    for (int i = 1; i < n; i ++ ) {
        int u = read (), v = read (), w = read ();
        addedge (u, v, w);
        addedge (v, u, w);
    }
    dfs (1, 0);
    l = p;
    max_d = 0;
    dep[p] = 0;
    dfs (l, 0);
    r = p;
    printf ("%lld\n", max_d);//开longlong
    bool flag = 0;
    for (int i = r; i; i = f[i]) vis[i] = 1;
    int ll = l, rr = r;
    for (int i = f[rr]; i != ll; i = f[i]) {
        int l_dis = dep[i], r_dis = dep[rr] - dep[i];
        dep[i] = max_d = 0;
        dfs2 (i, 0);
     //l找最右 r找最左 所以l只需要找一次就行了
        if (max_d == r_dis)
            r = i;
        if (max_d == l_dis && !flag) {
            flag = 1;
            l = i;
        }
    }
    int ans = 1;//为什么初始化ans = 1 因为后面 (i != l) 没有把l算进去
    for (int i = f[r]; i != l; i = f[i]) ans ++ ;
    cout << ans << endl;
    return 0;
}

评论

  • 还没有评论
作者: Object_ 更新时间: 2019-10-27 09:02  在Ta的博客查看 举报    0  

基本思路:

  • 题目要求树直径的必经边,那么首先应当获取一条直径.
  • 获取直径后从直径上的两个端点分别遍历一次直径,每次遍历直径时从直径上的每个点分别dfs一次并不经过直径上的点,如果深度可以被替换则说明非必经边.

#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
#define ll long long
using namespace std;
const int MAXN=2e5+10,MAXM=MAXN*2;
struct Edge{
    ll from,to,w,nxt;
}e[MAXM];
int head[MAXN],edgeCnt=1;
void addEdge(ll u,ll v,ll w){
    e[++edgeCnt].from=u;
    e[edgeCnt].to=v;
    e[edgeCnt].w=w;
    e[edgeCnt].nxt=head[u];
    head[u]=edgeCnt;
}
ll dep[MAXN];
bool vis[MAXN];
int n;
int from[MAXN];
bool inDiameter[MAXN];//是否在直径上
ll st,ed;//直径端点
void markDiameter(){//标记直径
    int tmp=ed;
    while(tmp){
        inDiameter[tmp]=1;
        tmp=from[tmp];
    }
}
ll bfs(int s){//求直径
    memset(dep,0,sizeof(dep));
    memset(vis,0,sizeof(vis));
    memset(from,0,sizeof(from));
    queue<int> q;
    q.push(s);
    vis[s]=1;
    while(!q.empty()){
        int nowU=q.front();
        q.pop();
        for(int i=head[nowU];i;i=e[i].nxt){
            int nowV=e[i].to;
            if(!vis[nowV]){
                dep[nowV]=dep[nowU]+e[i].w;
                vis[nowV]=1;
                from[nowV]=nowU;
                q.push(nowV);
            }
        }
    }
    ll ans=0,ansDep=0;
    for(int i=1;i<=n;i++){
        if(dep[i]>ansDep){
            ans=i,ansDep=dep[i];
        }
    }
    return ans;
}
ll dis_fromST[MAXN];//每个点到直径st端点的距离
bool vis_getDisFromST[MAXN];
void bfs_getDisFromST(){
    queue<int> q;
    q.push(st);
    vis_getDisFromST[st]=1;
    while(!q.empty()){
        int nowU=q.front();
        q.pop();
        for(int i=head[nowU];i;i=e[i].nxt){
            int nowV=e[i].to;
            if(!vis_getDisFromST[nowV]){
                vis_getDisFromST[nowV]=1;
                dis_fromST[nowV]=dis_fromST[nowU]+e[i].w;
                q.push(nowV);
            }
        }
    }
}
ll dis_fromED[MAXN];//每个点到直径ed端点的距离
bool vis_getDisFromED[MAXN];
void bfs_getDisFromED(){
    queue<int> q;
    q.push(ed);
    vis_getDisFromED[ed]=1;
    while(!q.empty()){
        int nowU=q.front();
        q.pop();
        for(int i=head[nowU];i;i=e[i].nxt){
            int nowV=e[i].to;
            if(!vis_getDisFromED[nowV]){
                vis_getDisFromED[nowV]=1;
                dis_fromED[nowV]=dis_fromED[nowU]+e[i].w;
                q.push(nowV);
            }
        }
    }
}
ll dep_noDiameter[MAXN];//不经过直径的最大深度
ll dfs_noDiameter(int x,int fa){
    ll maxDep=dep_noDiameter[x];
    for(int i=head[x];i;i=e[i].nxt){
        int nowV=e[i].to;
        if(nowV==fa||inDiameter[nowV])continue;
        dep_noDiameter[nowV]=dep_noDiameter[x]+e[i].w;
        ll tmp=dfs_noDiameter(nowV,x);
        maxDep=max(maxDep,tmp);
    }
    return maxDep;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n-1;i++){
        ll a,b,c;
        cin>>a>>b>>c;
        addEdge(a,b,c);
        addEdge(b,a,c);
    }
    st=bfs(1);
    ed=bfs(st);//直径
    cout<<dep[ed]<<endl;
    markDiameter();//标记直径上点
    bfs_getDisFromST();
    bfs_getDisFromED();//获取每个点到两个端点的距离
    int l=st,r=ed;//必经边端点
    int tmp=from[ed];
    while(tmp){//r
        if(tmp==st)break;
        dep_noDiameter[tmp]=0;
        ll nowMaxDep=dfs_noDiameter(tmp,0);
        if(nowMaxDep==dis_fromED[tmp]){
            r=tmp;
        }
        tmp=from[tmp];
    }
    bfs(ed);//重新获取from数组
    tmp=from[st];
    while(tmp){//l
        if(tmp==ed||tmp==r)break;
        ll nowMaxDep=dfs_noDiameter(tmp,0);
        if(nowMaxDep==dis_fromST[tmp])l=tmp;
        tmp=from[tmp];
    }
    int cnt=0;
    tmp=l;
    while(tmp){
        if(tmp==r)break;
        cnt++;
        tmp=from[tmp];
    }
    printf("%d\n",cnt);
    return 0;
}
 
反馈
如果你认为某个题解有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。