提出 #73718955

---

ソースコード 拡げる

#include <iostream>
#include <vector>
#include <stack>
#include <tuple>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int Q;
    cin >> Q;
    while(Q--) 
    {
        int N;
        cin >> N;
        vector<vector<int>> adj(N + 1);
        vector<int> deg(N + 1, 0);
        for (int i = 0;i < N - 1;i++) 
        {
            int A,B;
            cin >> A >> B;
            adj[A].push_back(B);
            adj[B].push_back(A);
            deg[A]++;
            deg[B]++;
        }
        vector<bool> is_valid(N + 1, false);
        for(int u = 1;u <= N;u++) 
            if(deg[u] >= 3) is_valid[u] = true;
        vector<bool> visited(N + 1, false);
        vector<int> dp(N + 1, 0); 
        int ans = 1; 
        for (int u = 1;u <= N;u++) 
        {
            if(is_valid[u] && !visited[u]) 
            {
                stack<tuple<int, int, bool>> st;
                st.emplace(u, -1, false);
                int current_max = 1;
                while (!st.empty()) 
                {
                    auto [curr,parent,processed] = st.top();
                    st.pop();
                    if (!processed) 
                    {
                        st.emplace(curr, parent, true);
                        visited[curr] = true;
                        for(auto it = adj[curr].rbegin(); it != adj[curr].rend();it++) 
                        {
                            int v = *it;
                            if(v != parent && is_valid[v])  st.emplace(v, curr, false);
                        }
                    } 
                    else 
                    {
                        int first = 0, second = 0;
                        for(int v : adj[curr]) 
                        {
                            if(v == parent || !is_valid[v]) continue;
                            int val;
                            if(deg[v] >= 4) 
                            {
                                val = dp[v] + 1;
                            } 
                            else 
                            {
                                val = 2;
                            }
                            if(val > first) 
                            {
                                second = first;
                                first = val;
                            } 
                            else if(val > second) 
                            {
                                second = val;
                            }
                        }
                        dp[curr] = max(1, first);
                        current_max = max(current_max, dp[curr]);
                        if(deg[curr] >= 4) 
                        {
                            int merge_len = first + second - 1;
                            current_max = max(current_max, merge_len);
                        }
                    }
                }
                ans = max(ans, current_max);
            }
        }
    	cout << ans << '\n';
    }
    return 0;
}

提出情報

ジャッジ結果