题意#
给定一棵 个点的有根树，根为 。
长度为 的序列 满足：
- ， 为 的祖先或 是 的祖先；
- ，.
求最长的序列 的长度。
分析#
#
大样例提示很明显。
对任意的二叉树（包括链），答案均为节点个数；对菊花图，答案为 。
#
上面的部分对正解提示也很明显。
容易发现，选序列的策略是：对于一个点 ，先选一个它的子树处理，再选其自己，再选另一个子树处理。
要让答案最大化，所以我们要选出两个答案最大的子树。
因此，我们用堆维护：对于子树中所有未被选取的点，将其（及其子树的一部分）选上之后，可以对增加的长度。
每次处理完之后，向上合并堆。（用可并堆或multiset）
上图序列 的选取方法如下：
被同一个节点选取的两个子树，其根节点颜色相同。无填充色即不选取。
代码#
#include <bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
using namespace __gnu_pbds;
const int MAXN = 100005;
int T, n;
vector<int> G[MAXN];
__gnu_pbds::priority_queue<int,less<int>,pairing_heap_tag>q[MAXN];
void dfs(int u,int father) {
for(int v:G[u]) {
if(v == father) continue;
dfs(v, u);
q[u].join(q[v]);
q[v].clear();
}
int x = 1;
for(int i = 1; i <= 2; i++)
{
if(q[u].empty()) break;
x += q[u].top(); q[u].pop();
}
q[u].push(x);
return;
}
void solve() {
scanf("%d", &n);
for(int i = 1; i < n; i++) {
int x, y;
scanf("%d%d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
dfs(1,0);
printf("%d\n", q[1].top());
for(int i = 1; i <= n; i++) {
G[i].clear();
q[i].clear();
}
return;
}
int main() {
scanf("%d", &T);
while(T--) solve();
return 0;
}