题解 | #爬#

T2

对于每个节点计算这个点的所有贡献。

非根节点统计自身和一级儿子点总数记为 $kk$，然后对于这 $kk$ 个点，每个点都有两种情况在这个点和不在这个店，拆开用位处理可得贡献和记为 $tmptmp$，然后只有一个蚂蚁的贡献要减去，所以贡献应当是 $tmp-sumtmp\; -\; sum$，然后这一块的贡献乘上 $2^{n-k-1}2^\{n\; -\; k\; -\; 1\}$ 就是总的贡献，其他 $k-1k\; -\; 1$ 除根节点每个点都有爬和不爬两种。

根节点的计算类似，讨论下就行，以下为代码。

# include <bits/stdc++.h>
# define int long long
# define wheneveright signed main
using namespace std;

const int maxn = 101005;
const int mod = 1000000007;

int KSM (int x, int y = mod - 2) {
	int ret = 1;
	while (y) {
		if (y & 1) ret = ret * x % mod;
		x = x * x % mod; y >>= 1;
	}
	return ret % mod;
}

struct reader {
	template <typename Type>
	reader & operator >> (Type & ret) {
		int f = 1; ret = 0; char ch = getchar ();
		for (;!isdigit (ch); ch = getchar ()) if (ch == '-') f = -f;
		for (; isdigit (ch); ch = getchar ()) ret = (ret * 10) + ch - '0';
		ret *= f; return * this;
	}
} fin;

int n, a[maxn], poe[maxn], sum, res;
vector < int > vec[maxn];

int fac[maxn], inv[maxn];
int C (int n, int m) { return fac[n] * inv[m] % mod * inv[n - m] % mod; }

int solve (const vector < int > & now, int m) {
	int ret = 0, k = (int) now.size (), tmp;
	for (int i = 0, p; i <= 30; i++) { p = tmp = 0; // 枚举位
		for (const int & j : now) if ((1 << i) & j) p++;
		if (m & (1 << i)) for (int j = 0; j <= p; j += 2) tmp += C (p, j);
		else for (int j = 1; j <= p; j += 2) tmp += C (p, j);
		ret += tmp % mod * poe[k - p + i] % mod;
	}
	return ret % mod;
}

wheneveright () {
	fin >> n; poe[0] = fac[0] = inv[0] = 1;
	for (int i = 1; i <= n + 100; i++) poe[i] = (poe[i - 1] << 1) % mod;
	for (int i = 1; i <= n; i++) inv[i] = KSM (fac[i] = fac[i - 1] * i % mod), fin >> a[i];
	for (int i = 2, x; i <= n; i++) fin >> x, vec[x].push_back (a[i]), vec[i].push_back (a[i]);
	res = (solve (vec[1], a[1]) - a[1]) % mod * poe[n - 1 - (int) (vec[1].size ())] % mod;
	for (int i = 2; i <= n; i++) { sum = 0;
		for (const auto & j : vec[i]) sum += j;
		res += (solve (vec[i], 0) - sum) % mod * poe[n - 1 - (int) (vec[i].size ())] % mod;
	}
	cout << (res % mod + mod) % mod << endl;
	return 0;
}