CF
Problem - E - Codeforces（二分好题）
二分找最大距离
check里直接放输出
注意要对a数组排序！！！
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int N=2e5+10;
LL a[N];bool check(LL n,LL k,LL x,LL d,bool tag){LL lst = 0,cnt=0;for (int i = 0; i < n;i++){if(a[i]-d>=lst){if(tag){for (int j = 0; cnt + j < k && lst + j <= a[i] - d;j++)cout << lst + j << " ";}cnt += a[i] - d - lst + 1;}lst = a[i] + d;}if(lst<=x){if(tag){for (int j = 0; cnt+j < k && lst + j <= x;j++){cout << lst + j << " ";}}cnt += x - lst + 1;}if(tag)cout << endl;return cnt >= k;
}void solve()
{LL n, k, x;cin >> n >> k >> x;for (int i = 0; i < n;i++){cin >> a[i];}sort(a, a + n);LL l = 0, r = x + 1;while(l+1<r){LL mid = l + r >> 1;if(check(n,k,x,mid,0))l = mid;elser = mid;}if(l==0){//特判，如果是0，直接按顺序输出即可for (int i = 0; i<k;i++){cout << i << " ";}cout << endl;return;}check(n, k, x, l, 1);
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--){solve();}
}
Problem - F - Codeforces
Roots change, but the tree stands strong — so should your logic.
发现自己连LCA都不知道，寒假要花时间学图论
要训练自己好好读题，并且能简洁总结题意的能力
题意：
对于1~n的每个根，计算其 k 个的点的不同的 LCA（最近公共祖先）的个数，并求和
求 :$$ \sum_{r=1}^{n} |S_r| = |S_1| + |S_2| + \cdots + |S_n| $$
题解都看了好久……（太菜了我）
理解：对于几个根使得 \(u\) 其为LCA ，先把1当根结点，然后换根。
- 根在 \(u\) 子树外（如果 \(u\) 子树的子结点能满足
sz[u]>=k,即u可以作为当前根的LCA，所以计算可能的根的数量，即 \(u\) 之外点的数量n-sz[u]。 - 根在 \(u\) 子树内（假设是 \(v\) ，想像把那个根提上来，如果 \(u\) 子树的子结点数变成
n-sz[v]，所以同上，当n-sz[v]>=k，则有sz[v]个根使得 \(u\) 为LCA）。 - 还有一种就是 \(u\) 为根，那就绝对满足，因为
k<=n。
tip：求每个根对k个点的不同的LCA，可以换成求每个点作为LCA时，可满足的根的数量
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int N=2e5+10;
vector<int> e[N];
LL ans;
int sz[N],n, k;void dfs(int u,int fa){sz[u] = 1;for(auto v:e[u]){if(v==fa)continue;dfs(v, u);sz[u] += sz[v];}for(auto v:e[u]){if(v==fa)continue;if(n-sz[v]>=k)//根在子树内ans += sz[v];}if(sz[u]>=k)//根在子树外ans += n - sz[u];
}void solve()
{cin >> n >> k;for (int i = 0; i <= n;i++){e[i].clear();}for (int i = 1; i < n;i++){int u, v;cin >> u >> v;e[u].push_back(v);e[v].push_back(u);}ans = 0;dfs(1, 0);cout << ans + n << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--){solve();}
}