E. Sending a Sequence Over the Network
题目：
思路：
贪心想不到时不妨考虑DP
我们发现我们既可以选左又可以选右，贪心好像也没什么思路，那么就不妨考虑dp
我们定义 dp[i] 为 1 ~ i 是否都能被构造出来，对于本题我们则有两种转移方式
①.如果我们选择 i 当左边，那么 i ~ i + b[i] 这一段就能被构造出来，则有 dp[i + b[i]] |= dp[i-1]，即继承上一层，如果上一层都构造不出来那么显然 1 ~ i + b[i] 是不可能构造出来的
②.如果我们选择 i 当右边，那么同理 1 ~ i - b[i] - 1 这段区间就要被构造出来，所以就有 dp[i] |= dp[i - b[i] - 1]
最后判断 dp[n] 是否为 1 即可，注意初始化 dp[0] = 1
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define Sunny 0
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
void solve()
{
int n;
cin >> n;
vector<int> b(n+1,0),dp(n+1,0);
for (int i = 1; i <= n; i++)
{
cin >> b[i];
}
dp[0] = 1;
for (int i = 1; i <= n; i++)
{
if(i + b[i] <= n) dp[i + b[i]] |= dp[i-1];
if(i - b[i] - 1 >= 0) dp[i] |= dp[i - b[i] - 1];
}
dp[n] ? yes : no;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return Sunny;
}D. Reset K Edges
题目：
思路：
套路题
看到最值想到二分，先探究二分性，显然如果 x 可以，那么 x + 1 肯定也可以，因此具有二分性
那么如何 check，其实这都是套路了，面对 树上删除+二分 的题，我们通常考虑从叶子节点出发，如果某一个地方不符合，那么立马删除，否则往上递归叠加
本题也是如此，我们不断记录以 u 为根的子树的最大高度 h[u]，那么如果对于某个节点 v，如果其子节点 son 满足，h[son] == mid，那么则需要删除这个连接子树的边，同时跳过记录这个子树，否则就可以不删，即继承子树高度看看是不是比原来更高
具体实现看代码，特别的，本题给的数据比较巧妙，我们可以直接枚举 n ~ 2 而不是递归形式求解高度
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define Sunny 0
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
void solve()
{
int n, k;
cin >> n >> k;
vector<vector<int>> g(n + 1);
for (int i = 2; i <= n; i++)
{
int fa;
cin >> fa;
g[fa].push_back(i);
}
vector<int> h(n+1,0);
auto check = [&](int x)->int{
int cnt = 0;
for (int i = 1; i <= n; i++)
h[i] = 1;
for (int i = n; i >= 2; i--)
{
for(auto & son : g[i])
{
if(h[son] == x) {
cnt++;
continue;
}
h[i] = max(h[i],h[son] + 1);
}
}
return cnt <= k;
};
int l = 1, r = 1e9;
while (l + 1 < r)
{
int m = l + r >> 1;
if (check(m))
r = m;
else
l = m;
}
if(check(l)) cout << l << endl;
else cout << r << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return Sunny;
}E. Hanging Hearts
题目：
思路：
比较吃思维
我们不难发现，在以 u 为根的子树，u 最后的权值一定是所有节点的最小值，那么可以想到一个显然的贪心，我们肯定是要在叶子放小的，依次往上放大的，因为如果要取走 u，那么其子树肯定要先取走，同时由于每次取完数后都是放数组最后，依次叶子放大的显然不优
那么考虑怎么让LIS最大，不难发现我们可以选择以 u 为根的一条最长子链做 u 的答案，这是答案的最小值，那么怎么才能让答案最大呢？
考虑两种情况
①. 如果我们要让 u 节点能为最后的 LIS 提供奉献，那么此时我们必须选 u，所以我们必须选一条包含 u 的最长子链最为答案，同时此时不能考虑其子树，因为 u 会变成其所有子树的最小值，那么如果考虑其余子树就不是最大子链的长度了
②. 如果我们不需要 u 节点为最后的 LIS 提供奉献，那么此时我们可以忽略 u 而将 u 的所有子节点的最大答案加入，因为每颗子树都是独立的，同时操作可以互相交换顺序，那么我们一定可以构造出一种方式使得答案能包含其所有子树的答案
具体实现看代码，其中 f 代表最长子链，dp 代表以 u 为节点的子树的最大奉献
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define Sunny 0
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int dp[100005],f[100005];
vector<vector<int>> g(100005);
int n;
void dfs(int fa)
{
f[fa] = 1;
for(auto & son : g[fa])
{
dfs(son);
f[fa] = max(f[fa],f[son] + 1);
dp[fa] += dp[son];
}
dp[fa] = max(dp[fa],f[fa]);
}
void solve()
{
cin >> n;
for (int i = 2; i <= n; i++)
{
int fa;
cin >> fa;
g[fa].push_back(i);
}
dfs(1);
cout << dp[1] << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
while (t--)
{
solve();
}
return Sunny;
}D. Sliding Tree
题目：
思路：
学到了求直径的新写法
我们最后要形成一个路径图，那么其实就是将树变成一条链
不难想到我们可以求出树的直径，然后考虑将直径的长度变为 n
最优的办法肯定是每次操作都能使得树的直径长度增加，那么如何选择呢？
对于这种情况，我们如何使得一次就让直径增加？其实不难想到，我们只需要以度数为 3 的那个点为 b，其不在直径上的点为 c，然后任意选左右一个当作 a，即可，那么这样就能使得直径增加了，如下图
所以直接模拟即可，具体实现看代码，可以学习一下求直径的好方法
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define Sunny 0
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
void solve()
{
int n;
cin >> n;
vector<vector<int>> g(n + 1);
vector<int> deg(n + 1, 0);
int flag = 1;
for (int i = 0; i < n - 1; i++)
{
int u, v;
cin >> u >> v;
g[u].push_back(v), g[v].push_back(u);
deg[u]++, deg[v]++;
if (deg[u] > 2 || deg[v] > 2)
flag = 0;
}
if (flag)
{
cout << "-1\n";
return;
}
vector<int> dis(n + 1, 0), father(n + 1, 0);
auto dfs = [&](auto &&self, int fa, int se) -> void
{
father[se] = fa;
dis[se] = dis[fa] + 1;
for (auto &son : g[se])
{
if (son == fa)
continue;
self(self, se, son);
}
};
dfs(dfs, 0, 1);
int root1 = max_element(dis.begin() + 1, dis.end()) - dis.begin();
dfs(dfs, 0, root1);
int root2 = max_element(dis.begin() + 1, dis.end()) - dis.begin();
vector<int> ind(n+1,0);
int now = root2;
while (now)
{
ind[now] = 1;
now = father[now];
}
for (int i = 1; i <= n; i++)
{
for(auto & son : g[i])
{
if(ind[i] && !ind[son])
{
cout << father[i] << " " << i << " " << son << endl;
return;
}
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return Sunny;
}