点击输入文字 - P14467 Sol

注意到每个人扔给的人是固定的，所以

k

次后的局面是唯一确定的。观察我们每次进行的变换：

a_i \leftarrow \sum_{s_j = i} a_j

球是沿着基环树森林传递的，可以联想到一个 Trick：在基环树上倍增，求出

k

级儿子。

CPP

rep(j, 1, 31) rep(i, 1, n) st[i][j] = st[st[i][j - 1]][j - 1];

我们将

k

分解为

\sum 2^iop_i

，每次都用倍增预处理，由于是同一变换的重复，所以变换的顺序是无关的。

CPP

rep(j, 0, 30) if(k & (1 << j)) {
      rep(i, 1, n) f[i] = 0;
      rep(i, 1, n) f[st[i][j]] += a[i];
      rep(i, 1, n) a[i] = f[i];
   }

P.S.：这题出在某校模拟赛里，然后我因为输出用换行隔开而非空格狂砍 -38 分。

code:

CPP

# include<bits/stdc++.h>
# define rep(i,a,b) for(int i = (a);i <= (b);i ++)
# define dwn(i,a,b) for(int i = (a);i >= (b);i --)
# define fid(i,a,F) for(int i = (a);F;i ++)
# define int32 int
# define int64 long long
# define int16 short
# define dbg(x) std::cerr << #x << ":" << x <<"\n";
# define FaILurEg(s) std::freopen(s".in","r", stdin);std::freopen(s".out","w",stdout);
# define ___main int32 main()
using std::cin;using std::cout;
int n, k, a[100005], st[100005][32], f[100005];
___main {
//	FaILurEg("krugo");
   std::ios::sync_with_stdio(0);cin.tie(0);
   cin >> n >> k;rep(i, 1, n) cin >> a[i];rep(i, 1, n) cin >> st[i][0];
   rep(j, 1, 31) rep(i, 1, n) st[i][j] = st[st[i][j - 1]][j - 1];
   rep(j, 0, 30) if(k & (1 << j)) {
      rep(i, 1, n) f[i] = 0;
      rep(i, 1, n) f[st[i][j]] += a[i];
      rep(i, 1, n) a[i] = f[i];
   } 
   int mx = 0; rep(i, 1, n) mx = std::max(mx, a[i]);cout << mx << "\n";
   rep(i, 1, n) if(a[i] == mx) cout << i << "\n";
}

点击输入文字 - P14467 Sol

文章操作

相关推荐

评论

点击输入文字 - P14467 Sol