P3884 二叉树问题 题解

· · 题解

update 2024.9.27 修复挂掉的图

P3884 二叉树问题

传送门

本蒟蒻第一篇题解，前面的大佬都是 lca+dfs 或者 Floyd 做的，我不会lca，只能自己想了一个较为精巧的思路，不喜勿喷。

思路

我们可以将每两个点之间的边建为双向的，以一为根节点，则就有向上（蓝色）和向下（红色）两种边。

显然，从根节点遍历时所经过的都是红色边，蓝色边如何处理无关痛痒。先由 u 到 v 遍历边，所经过的红色边就是 指向叶子结点的边 （指向根结点的边都是蓝色的），可以把他们标记为 1 （题中只需要加他们的一倍）；再由 v 到 u 遍历一次边，所经过的红色边就是 指向根节点的边 （指向叶子结点的都是蓝色的），标记为 2 （题中要求加他们的两倍）。然后再从根节点向下深搜，把每条边的标记加起来就好。

代码（附上关键注释）

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

int a[110],idx;
int st[110];
int h[110],ne[220],e[220];
int size[110];
int x,y;


//建边
void add(int a,int b){
    ne[idx]=h[a],e[idx]=b,h[a]=idx++;
}


//搜索深度和宽度
int dfs(int u,int deep,int fa){
    size[deep]++;//深度为deep的宽度
    int d=deep;
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(j==fa)continue;
        d=max(d,dfs(j,deep+1,u));//取最深的深度
    }
    return d;
}


//累加标记的边
int dfss(int u,int fa){
    int ans=0;
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(j==fa)continue;//保证不向上
        ans+=st[i];
        ans+=dfss(j,u);
    }
    return ans;
}


//搜索u->v或者v->u
bool query(int u,int en,int last,int flag){
    if(u==en){
        return true;//搜到目标点
    }
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(j==last)continue;
        if(query(j,en,u,flag)){//搜到了才能标记
            st[i]=flag;//标记不同类型的边
            return true;
        }
    }
    return false;
}


signed main(){
    int n;
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=1;i<n;i++){
        int l,r;
        cin>>l>>r;
        add(l,r),add(r,l);//建双向边
    }


    int deep=dfs(1,1,0);//搜深度和宽度
    int res=0;
    for(int i=1;i<=deep;i++){
        res=max(res,size[i]);
    }
    cin>>x>>y;
    cout<<deep<<endl<<res<<endl;


    query(y,x,0,2);//u到v
    query(x,y,0,1);//v到u

    cout<<dfss(1,0);
    return 0;
}

完美收官~

管理大大求过QAQ