1 solutions
-
0
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = 0x3f3f3f3f3f3f3f3f; typedef multiset<ll>::iterator itt; const int N = 5e5+11, P = 998244353; int n; ll f[N], ans; int tot, head[N], ver[N], nex[N]; void add(int x, int y){ nex[++tot] = head[x]; head[x] = tot; ver[tot] = y; } void dfs(int x, int fa){ ll cnt = 0; for(int i=head[x]; i; i=nex[i]) if(ver[i] != fa){ int y = ver[i]; cnt ++; dfs(y, x); } if(!cnt) {f[x] = 0; return ;} for(int i=head[x]; i; i=nex[i]) if(ver[i] != fa){ f[x] = max(f[x], max(1ll, f[ver[i]]) + cnt - 1); } ans = max(ans, f[x] + (fa ? 1 : 0)); if(cnt < 2) return; ll q[cnt+11], t = 0; for(int i=head[x]; i; i=nex[i]) if(ver[i] != fa){ q[t++] = f[ver[i]]; } sort(q, q + t); ans = max(ans, q[t-1] + q[t-2] + cnt - 2 + (fa ? 1 : 0)); } void work(){ scanf("%d",&n); tot = 0, ans = 1; for(int i=1;i<=n;i++) f[i] = head[i] = 0; for(int x,y,i=1;i<n;i++) scanf("%d%d",&x,&y), add(x, y), add(y, x); dfs(1, 0); // printf("ans=%lld\n",ans); printf("%lld\n",ans); } int main(){ int t = 1; scanf("%d",&t); while(t--) work(); return 0; }
- 1
Information
- ID
- 531
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 10
- Tags
- # Submissions
- 10
- Accepted
- 1
- Uploaded By