当前位置：首页 > news >正文

HBCPC2025 补题（F、I)

news 2025/5/21 14:42:40

HBCPC2025 补题

补题连接:Codeforces

I 感染

做法1：std做法：树上dp统计贡献找最大

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define int long long
#define pb push_back
#define pii pair<int,int>
#define FU(i, a, b) for(int i = (a); i <= (b); ++ i)
#define FD(i, a, b) for(int i = (a); i >= (b); -- i)
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const int maxn= 5e5+5,MAXN = maxn;int n;
vector<int> G[maxn];
int s[maxn];
int f[maxn];
int dep[maxn];
int sum1=0;void dfs1(int x,int fa){dep[x]=dep[fa]+1;for(int e:G[x]){if(e==fa)continue;dfs1(e,x);s[x]+=s[e];}
}void dfs2(int x,int fa){for(int e:G[x]){if(e==fa)continue;f[e]=f[x]+sum1-2*s[e];dfs2(e,x);}
}void solve() {cin>>n;sum1=0;memset(f,0,sizeof(f));for(int i=1;i<=n;i++){G[i].clear();}for(int i=1;i<n;i++){int u,v;cin>>u>>v;G[u].pb(v);G[v].pb(u);}for(int i=1;i<=n;i++){s[i]=G[i].size();sum1+=s[i];}dep[0]=-1;dfs1(1,0);for(int i=1;i<=n;i++){f[1]+=dep[i]*G[i].size();} dfs2(1,0);int maxans=0;vector<int>ans;for(int i=1;i<=n;i++){int tans = n*sum1-f[i];if(tans==maxans){ans.pb(i);}else if(tans > maxans){maxans = tans;ans.clear();ans.pb(i);}}cout<<ans.size()<<endl;for(int e:ans){cout<<e<<" ";}cout<<endl;
}	signed main() {
#ifdef ONLINE_JUDGE
#elsefreopen("../in.txt", "r", stdin);
#endifcin.tie(0)->ios::sync_with_stdio(0);int T = 1;cin >> T;while (T--) {solve();}return 0;
}

做法2：猜结论要找的是树的重心，于是答案只可能有1或2个点。这个真的是神人了，赛时其实猜到了但被骗了于是把自己否了。

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;const int N = 500010;
int n, ans = N;
vector<int> g[N];
int Size[N], weight[N], centroid[2];void GetCentroid(int cur, int fa) {Size[cur] = 1;weight[cur] = 0;for (int v : g[cur]) {if (v != fa) {GetCentroid(v, cur);Size[cur] += Size[v];weight[cur] = max(weight[cur], Size[v]);}}weight[cur] = max(weight[cur], n - Size[cur]);if (weight[cur] <= n / 2) {centroid[centroid[0] != 0] = cur;}
}int main() {int T;cin >> T;while (T--) {cin >> n;centroid[0]=0,centroid[1]=0;for(int i=1;i<=n;i++){g[i].clear();Size[i]=0;weight[i]=0;}for (int i = 0; i < n - 1; i++) {int a, b;cin >> a >> b;g[a].push_back(b);g[b].push_back(a);}GetCentroid(1, 0);int a = centroid[0], b = centroid[1];if (a > b)swap(a, b);if (a && b) {cout << 2 << endl;cout << a << " " << b << endl;} else {cout << 1 << endl;cout << b << endl;}}return 0;
}

F 不死国的生命树

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define int long long
#define pb push_back
#define pii pair<int, int>
#define FU(i, a, b) for (int i = (a); i <= (b); ++i)
#define FD(i, a, b) for (int i = (a); i >= (b); --i)
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6 + 5, MAXN = maxn;
int n;
int a[maxn];
int fa[maxn];
int up[maxn][21]; // 2^(i-1)
int dep[maxn];
vector<int> G[maxn];
int j[maxn];
void dfs(int x) {for (int e : G[x]) {dep[e] = dep[x] + 1;dfs(e);}
}
void dfs1(int x) {int oldj = j[a[x]]; // 保存当前状态j[a[x]] = x;up[x][1] = j[a[x] + 1];for (int i = 2; i <= 20; i++) {if (up[x][1] == 0)break;up[x][i] = up[up[x][i - 1]][i - 1];if (up[x][i] == 0)break;}for (int e : G[x]) {dfs1(e);}j[a[x]] = oldj;
}
int query(int s, int t) {int ans = 1;while (dep[s] > dep[t]) {int k = 0;for (int i = 20; i >= 1; i--) {if (up[s][i] != 0 && dep[up[s][i]] >= dep[t]) {k = i;break;}}if (k == 0)break;ans += 1 << (k - 1);s = up[s][k];}return ans;
}void solve() {cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];up[i][0] = i;}fa[1] = -1;for (int i = 2; i <= n; i++) {cin >> fa[i];G[fa[i]].pb(i);}dep[0] = -1;dep[1] = 0;dfs(1);dfs1(1);int Q;cin >> Q;while (Q--) {int s, t;cin >> s >> t;cout << query(s, t) << endl;}
}signed main() {cin.tie(0)->ios::sync_with_stdio(0);
#ifdef ONLINE_JUDGE
#elsefreopen("../in.txt", "r", stdin);
#endifint T = 1;while (T--) {solve();}return 0;
}