直徑 HYSBZ - 3124

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

第一問求樹的直徑 第二問求有多少邊被所有直徑覆寫

求第一問時把直徑上的點存下來 枚舉直徑上的點 求一下不走直徑上的點所能到達的最遠距離 記為dis3 如果和直徑的左端點距離相等 就把目前點到左端點的邊都标記 這些邊就是不符合條件的 和直徑的右端點距離相等同樣處理

要求的邊時被所有直徑覆寫的 如果有某個點的dis3等于到左右端點的距離 說明存在另外一條直徑 該點到端點上的這些邊沒有被另外一條直徑覆寫

複雜度還是o(n)的 因為不能走直徑就相當于把這顆樹分成了很多不連通的小部分 非直徑上的點隻會被走一次

#include <bits/stdc++.h>
using namespace std;
#define ll long long

struct node
{
    int v;
    ll w;
    int next;
};

node edge[400010];
ll dis1[200010],dis2[200010],dis3[200010];
int first[200010],fa1[200010],fa2[200010],book[200010],pre[200010];
int n,num;

void addedge(int u,int v,ll w)
{
    edge[num].v=v;
    edge[num].w=w;
    edge[num].next=first[u];
    first[u]=num++;
}

void dfsI(int cur,int &p)
{
    ll w;
    int i,v;
    for(i=first[cur];i!=-1;i=edge[i].next)
    {
        v=edge[i].v,w=edge[i].w;
        if(v!=fa1[cur])
        {
            dis1[v]=dis1[cur]+w,fa1[v]=cur;
            dfsI(v,p);
            if(dis1[p]<dis1[v]) p=v;
        }
    }
}

void dfsII(int cur)
{
    ll w;
    int i,v;
    for(i=first[cur];i!=-1;i=edge[i].next)
    {
        v=edge[i].v,w=edge[i].w;
        if(v!=fa2[cur])
        {
            dis2[v]=dis2[cur]+w,fa2[v]=cur;
            dfsII(v);
        }
    }
}

void dfsIII(int cur,ll &maxx)
{
    ll w;
    int i,v;
    for(i=first[cur];i!=-1;i=edge[i].next)
    {
        v=edge[i].v,w=edge[i].w;
        if(book[v]==0)
        {
            dis3[v]=dis3[cur]+w,book[v]=1;
            maxx=max(maxx,dis3[v]);
            dfsIII(v,maxx);
        }
    }
}

int main()
{
    ll w,maxx,ans1;
    int i,j,u,v,p1,p2,p,ans2;
    scanf("%d",&n);
    memset(first,-1,sizeof(first));
    num=0;
    for(i=1;i<=n-1;i++)
    {
        scanf("%d%d%lld",&u,&v,&w);
        addedge(u,v,w);
        addedge(v,u,w);
    }

    dis1[1]=0,fa1[1]=0;
    p1=0;
    dfsI(1,p1);
    dis1[p1]=0,fa1[p1]=0;
    p2=0;
    dfsI(p1,p2);
    ans1=dis1[p2];
    //printf("***%d %d***\n",p1,p2);

    dis2[p2]=0,fa2[p2]=0;
    dfsII(p2);

    p=p1,num=0;
    while(p!=0)
    {
        pre[++num]=p;
        book[p]=1;
        p=fa2[p];
    }

    p=p1;
    while(p!=0)
    {
        dis3[p]=0;
        maxx=0;
        dfsIII(p,maxx);
        dis3[p]=maxx;
        p=fa2[p];
    }

    /*
    printf("***%d***\n",num);
    for(i=1;i<=num;printfi++)
    {
        printf("*%d %lld %lld %lld*\n",pre[i],dis1[pre[i]],dis2[pre[i]],dis3[pre[i]]);
    }
    */

    memset(book,0,sizeof(book));
    for(i=1;i<=num;i++)
    {
        if(dis3[pre[i]]==dis1[pre[i]]) for(j=i-1;j>=1&&book[j]==0;j--) book[j]=1;
    }
    for(i=num;i>=1;i--)
    {
        if(dis3[pre[i]]==dis2[pre[i]]) for(j=i;j<=num-1&&book[j]==0;j++) book[j]=1;
    }

    ans2=0;
    for(i=1;i<=num-1;i++) ans2+=(book[i]==0);

    printf("%lld\n%d\n",ans1,ans2);

    return 0;
}