P3304 [SDOI2013]直径 题解


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

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

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

评论

  • 荔枝君
    惧聚聚聚聚聚聚聚聚%%%%%%
  • 荔枝君
    %%%%%%%%%
  • 我不认识你
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  • AllanGong
    TQLTQL%%%ORZORZ
  • 我不认识你
    太~强~了!~
  • 我是蒟弱
    什么orz,什么%%%,都不够
  • 我是蒟弱
    大~丶~弓~虽~了~!
  • 我是蒟弱
    用一个个 一、丨、丿、丶写出绝妙题解!
  • 我是蒟弱
    Good solution!
  • yangyucheng66
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%
作者: wu3412790 更新时间: 2018-10-26 13:40  在Ta的博客查看 举报    15  

这道题用到了一个非常有用的引理,树的所有直径拥有相同的中点!NOI2013有个叫快餐店的题也可以用这个引理。

这里中点可能在一条边的内部。证明的话用反证法,大家自己一画就明白。

这样一来,随便找一条直径,如果中点在某条边内部,那么这条边毫无疑问是在所有直径上的,然后我们去掉这条边,在剩下的两棵有根树里分别找从根到叶子的最长路上哪些边是必须的,递归解决即可。这个子问题非常有用,我们在这里叫他RootLeafPath。

另一种情况是中点是某个顶点,这时我们以中点为根dfs,那么所有直径都经过根,怎么看哪些边是必须的呢?显然要挑两个根的儿子往下走,我们设f[x]表示从一个节点向下走的最大深度,并挑出根的儿子中f[x]+(根到x的边权)中前三大的,不妨设他们是a,b,c。分为三种情况|:(1)如果b>c,那么在a,b对应的子树里做RootLeafPath即可。 (2)如果a>b=c,那么只在a对应子树里做RootLeafPath即可。 (3)如果a=b=c,这时没有任何一条边是必须的,输出0。

#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); 
        add(a,b,c);
        add(b,a,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
    多谢大佬写得通俗易懂%%%
  • chill
    noob
  • M_sea
    唯一一篇看懂的题解(逃
  • 1517460958dyc
    您的变量命名再改改就更通俗易懂了(逃
  • Zekrom
    JU(逃
作者: 破壁人 更新时间: 2018-01-04 19:49  在Ta的博客查看 举报    10  

首先求出直径这个简单,只要dfs一遍就行了。

我们再考虑第二问。要求的是所有直径都经过的边数。

所以我们先任意求出一条直径,记录这条直径上的点。

再对每个直径上的点都dfs,求出以这个点为起点的最长链(当然不能包括直径上的其它点),长度用dis[i]表示。

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

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

从左端点开始向右遍历直径,若到了j号点发现,dis[j]=rs[j]就可以跳出循环,因为j的右边的所有边都不可能是必经边。

因为我们找到了一条不经过它们的直径。

那么是不是左端点到j就是必经边了呢?显然不是的。

因为还有可能出现这种情况,即dis[k]=ls[k],这样就变成了k的左边的所有边都不可能是必经边。

所以我们还要类似的从刚才跳出循环的点开始向左寻找这个k点。

那么j到k的所有边就是必经边了。

#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
作者: _J_C_ 更新时间: 2018-07-19 19:56  在Ta的博客查看 举报    6  

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

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

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

题意是给定一棵有权的树,求树的直径大小及有多少边在所有直径中都出现了。

首先先随便找一条直径。稍微具体的说就是先任意选取一个点,bfs/dfs出树上离这个点最远的一个点right(可能有多个,但一个就好),然后在以right为起点重复bfs/dfs一次,得到left。那么left

与right就是树上某一条直径的两端了。(证明略←w←)

好了,我们找到了一条直径。我们不妨把它看做是直的

对,就中间最粗的那个条,就是我们找到的直径。

看下面,我们发现了一处很不和谐的地方:(红色圈内)

哪里不和谐呢?这两条边看(ji)上(suan)去(chu)是相等的!

这意味这什么呢,这说明这里还有一条隐藏的树的直径:

而很显然的是:这两条直径有分叉,或者说不相交的地方:

那么这个分叉点之下就都没机会了,因为已经有两条直径不在这边相交了,可以丢了。

如果我们对left与right(上文中我们找到的树的直径的两端)间任意一点都判断了它是否分叉,最后我们就能得到一个不分叉的区间,区间内所有的边就是我们要的答案了。

为什么呢?因为所有直径间必然互相有交点(否则,交叉的“直径”可以通过连接它们的边“取长补短”从而延长)。所以我们只要沿着当前直径间的点走,向两侧延伸查找最长距离,判断是否分叉即可保证我们考虑了所有的直径与所有可能被所有直径经过的边。

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

考虑一下如何实现。

建图就不多说了,记得加双向边和开两倍数组(邻接表)。

首先用广搜bfs(int start, int& faraway)找到距离start最远的点faraway。具体的实现方式是用bVis[]表示这个点是否被访问过(树上广搜时不可能返回,又不是有环图的最短路233),用dis[]表示从start搜到当前点的距离。如果dix[x]>dis[faraway],则更新faraway。

对于这个bfs,更加具体的细节是:faraway先初始化为0,因为没有0号点,dis[0]一直是0,很“容易”被更远的点覆盖。

更值得一提的是,这个用驼峰命名法出来的bVis[]居然不是bool,而是个int,而且还要用一个NextVis与它比较。这是因为我们需要多次使用bVis[]数组(还有下面的dfs呢),每次使用当然都要初始化它,这就浪费了大把的时间。我的做法是使用一个变量NextVis来代表真值——如果bVis[x]==NextVis,则为真:否则为假。这样子每次初始化只要++NextVis就好了。(这样子跑出来670ms,每次都memset跑出来是3576ms)当然,读者可能有不同的操作来避免反复初始化,或者有根本不需要这个数组的做法233。

还有就是为了知道这个点是否分叉,我们需要知道它到直径左、右端点的距离。如果这个距离等于它向侧面延伸出去的最长长度,那么就分叉了。(如果这个距离小于它延伸的最长长度,恭喜你,直径找错了)而且同时我们最好先把left与right间的点分出来,这样处理起来方便。

我的做法是在bfs时使用链表forward[x]记录x这个点是从哪里走过来的,并用disforward[x]记录走过来的边长(或者直接查找也行,毕竟这是一棵树)。在解析时沿着forward[x]走并写入mid[],累加/累减得到它到两端点的距离并用end存mid里有多少个元素,同时标记bInList表示它在直径里。

烦人的bfs和解析终于过去了,现在考虑一下怎么让一个点找到向侧面延伸的最长长度length[]。这个简直就是搜索。在点x处枚举它相邻的点,并排除相邻点在直径内的情况,dfs递归并从这些点中取出一个最大值。

最后,用for循环枚举mid里所有点,依次调用dfs,比较长度得知是否分叉;获取左右极限点后就可以输出答案了(看着洛谷AC的花蹦出来真是一件快乐的事情23333

顺便说一句,记得long long……(并不知道不写会不会过,但是200000个点,边权在1e9内怕还是很玄

如果还有疑惑,下面还有完整的、加了注释的代码:

#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 iHead[212345];//邻接表

int iEnd(2);

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

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);
        add(fr, to, len);
        add(to, fr, 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 :)

忽然想起来,dfs之前是可以不用memset的,因为它能搜到的位置被直径限制了……所以即使memset,用的好也不用3700ms。 ]

评论

  • 顾月
    tql.!
  • COUPDETAT
    %%%
  • COUPDETAT
    1551看不懂
  • 姝雨墨
    垃圾!
作者: 姝雨墨 更新时间: 2019-06-24 11:54  在Ta的博客查看 举报    3  

【luogu-3304】【SDOI2013】直径

前提

我们需要明确以下几个条件:

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

    思路

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

    求法

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

这端点是什么呢

就是各直径在这条重合路径同侧的端点的LCA

例子就是上图中,第一条路径是$3-2$,第二条路径是$3 - 6$,重合路径是$3-4$。 两条直径的端点$6$和$2$在重合路径$3-4$的同侧。我们只需要求端点$6$和$2$的LCA即点$4$就是重合路径的一个端点。

同理,求出另一个端点即可。

特殊地,对于一个点的LCA就是它本身。

但是多个点的LCA我不会用倍增求……呜呜呜呜呜。

然后用欧拉序求出LCA即可,然后求两个LCA的距离。

代码

/*!
 * FileName: luogu-3304.cpp
 * This Problem is on luogu. The ID of the problem is 3304. 
 * Copyright(c) 2019 Shu_Yu_Mo
 * MIT Licensed
 * 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;
inline int read()
{
    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;
int head[_N];
void add(int u, int v, int w)
{
    edge[++tot].nxt = head[u];
    edge[tot].node = v;
    edge[tot].w = w;
    head[u] = tot;
}
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++)
    {
        int tmpx = read(), tmpy = read(), tmpz = read();
        add(tmpx, tmpy, tmpz);
        add(tmpy, tmpx, tmpz);
        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的边数
作者: cqqqwq 更新时间: 2018-05-12 20:59  在Ta的博客查看 举报    5  

题意

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

给定的一棵$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;   
}
 
反馈
如果你认为某个题解有问题,欢迎向洛谷反馈,以帮助更多的同学。



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