oldsu 的博客

oldsu 的博客

NotOnlyHAPPY

题解 P3304 【[SDOI2013]直径】

posted on 2019-06-24 11:54:11 | under 题解 |

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