【枚举边+树的直径】CF14D

比眉伴天荒 2024-03-23 00:23 70阅读 0赞

[Problem - 14D - Codeforces][]

题意：

![fe2da99906ca4bcd9783bdf0d72af0ca.png][]

![9f900732e65b489fae2b0becd799cb1c.png][]

思路：

两条链不相交，说明是在不同连通分量中，我们可以枚举边来把树分为两个连通分量，然后分别计算直径即可

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e5+10;
    const int mxe=1e5+10;
    const int mxv=1e5+10;
    const int mod=1e9+7;
    const int Inf=1e18;
    
    vector<int> G[mxn];
    
    int res=1,ans1,ans2;
    int N,u[mxn],v[mxn];
    int a[mxn];
    int dp[mxn][3];
    
    void dfs(int u,int fa,int mode){
        dp[u][1]=dp[u][2]=0;
        for(auto v:G[u]){
            if(v==fa) continue;
            dfs(v,u,mode);
            if(dp[v][1]+1>=dp[u][1]){
                dp[u][2]=dp[u][1];
                dp[u][1]=dp[v][1]+1;
            }else if(dp[v][1]+1>=dp[u][2]) dp[u][2]=dp[v][1]+1;
        }
        if(mode==1) ans1=max(ans1,dp[u][1]+dp[u][2]);
        else ans2=max(ans2,dp[u][1]+dp[u][2]);
    }
    void solve(){
        cin>>N;
        for(int i=1;i<=N-1;i++){
            cin>>u[i]>>v[i];
            G[u[i]].push_back(v[i]);
            G[v[i]].push_back(u[i]);
        }
        int ans=0;
        for(int i=1;i<=N-1;i++){
            ans1=0,ans2=0;
            dfs(u[i],v[i],1);
            dfs(v[i],u[i],2);
            ans=max(ans,ans1*ans2);
        }
        cout<<ans<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[Problem - 14D - Codeforces]: https://codeforces.com/problemset/problem/14/D
[fe2da99906ca4bcd9783bdf0d72af0ca.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/204f5d979a314a29ab55f71bba942da2.png
[9f900732e65b489fae2b0becd799cb1c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/1bb7bd7ed3f84672ab14b7bac7070c22.png