D. Maximize the Root

題目：

?

思路：

樹上二分，中下題

我們可以發現如果 x 可以，那么 x - 1 肯定也可以，所以可以直接二分答案

具體的，我們每次二分能增加的值 mid ，如果 a[i] < mid，那么子樹就要 a[i] + a[i] - mid 個，否則直接遞歸子樹即可，以此類推，具體實現看代碼

代碼：

#include <iostream>
#include <algorithm>
#include<cstring>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <memory>
using namespace std;
#define int long long
#define yes cout << "Yes\n"
#define no cout << "No\n"void solve()
{int n;cin >> n;vector<int> a(n + 1);vector<vector<int>> g(n + 1);for (int i = 1; i <= n; i++){cin >> a[i];}for (int i = 2; i <= n; i++){int p; cin >> p;g[p].push_back(i);}if (n == 1){cout << a[1] << endl;return;}auto check = [&](int need) ->bool{int flag = 1;auto dfs = [&](auto self,int fa,int needval) ->void{if (!flag){return;}if (fa != 1)needval += max(needval - a[fa], 0LL);if (needval > a[fa] && g[fa].empty() || needval > 1e9){flag = 0;return;}for (auto& son : g[fa]){self(self, son, needval);}};dfs(dfs, 1, need);return flag;};int l = 0, r = 1e9;while (l + 1 < r){int mid = l + r >> 1;if (check(mid)){l = mid;}else{r = mid;}}if (check(r)){cout << a[1] + r << endl;return;}cout << a[1] + l << endl;
}signed main()
{cin.tie(0)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}

---

C. Serval and Toxel's Arrays

題目：

思路：

很考驗實現方式的一題

遇到這種題，我們要知道拆分，即把每個數的奉獻算出來再累加即可

對于一個數 x，如果 我們選了一個 沒有 x 的數組，那么奉獻就是 1，取有 x 的數列，奉獻也是 1，但是這是兩種不同的取法，所以我們可以分開計算（特別的一共有 m + 1個數組，因為還有初始數組）

對于第一種取法，那么就是 cnt += xhas * (m + 1 - xhas)，其中 xhas 為 x 的數量

對于第二種取法，有 cnt += xhas * (xhas-1) / 2

由于 n + m 不是很大，所以枚舉 n+m 的每一個數是可行的，那么如何快速計算 xhas 成了問題

我們可以這樣想，由于每次只改變一個數，那么也就是說如果某個數一直沒改變，那么最后肯定有 m + 1 個，而如果中間改變過，那么肯定在改變之前這個數就一直存在了，也就是連續的某一段全含有 x，所以我們可以存儲 last[i] 代表上一個數是否存在，以及如果存在它的位置在哪里

這樣我們就解決了 xhas 的問題，具體實現看代碼

代碼：

#include <iostream>
#include <algorithm>
#include<cstring>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <memory>
using namespace std;
#define int long long
#define yes cout << "Yes\n"
#define no cout << "No\n"void solve()
{int n, m;cin >> n >> m;vector<int> a(n+1),last(n+m+1,-1),cnt(n+m+1,0);for (int i = 1; i <= n; i++){cin >> a[i];last[a[i]] = 0;}for (int i = 1; i <= m; i++){int p, v;cin >> p >> v;if (a[p] != v){cnt[a[p]] += i - last[a[p]];last[a[p]] = -1;last[v] = i;a[p] = v;}}int res = 0;for (int i = 1;i <= n+m;i++){if (last[i] != -1){cnt[i] += m - last[i] + 1;}}for (int i = 1; i <= n + m; i++){res += cnt[i] * (m + 1 - cnt[i]);res += cnt[i] * (cnt[i] - 1) / 2;}cout << res << endl;
}signed main()
{cin.tie(0)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}