「联合省选 2020 A」树

按位考虑。

对于一个点来说，其儿子到其的距离是 \(dep_v-u\)。

那么其儿子做出的贡献是 \(V_v+dep_v-dep_u\)。

在模 \(2^{i+1}\) 的意义下若 \(2_i\le V_v+dep_v-dep_u< 2^{i+1}\) 则 \(v\) 会对 \(u\) 产生一个 \(2^i\) 的贡献。

也就是说，我们求出以 \(u\) 为根的子树中所有点的 \(V_v+dep_v\) 的桶并且对 \([2^i+dep_u.2^{i+1}+dep_u)\) 这个区间内做一个统计即可。

注意，这里的区间都应该是在模 \(2^{i+1}\) 的意义下的，而我们上述式子在代码中应该转换成模 \(2^{i+1}\) 意义下。具体细节看代码（也就是可能统计区间是分两段的，也就是 \([l,2^{i+1})\cup[1,r]\)，由于 \(V_v+dep_v\) 一定大于 \(dep_u\) ，所以 \([1,r]\) 这段区间是有意义的）

求出以 \(u\) 为根的子树中所有点权值的桶是一个经典问题，我们可以 dfs 一遍，然后将进入 \(u\) 和从 \(u\) 出去的桶做一个差分即可得到。

复杂度 \(O(n\log^2 V)\)。

代码如下：

#include
#define ll long long
using namespace std;
const int MAXN = (1<<21)+5;
const int MX = (1<<21);
bool Small;
struct BIT
{
	#define lowbit(i) (i&(-i))
	int t[MAXN],mx;
	BIT(){memset(t,0,sizeof t);}
	void upd(int p,int x){for(int i=p;i<=mx;i+=lowbit(i))t[i]^=x;}
	ll que(int p){ll r=0;for(int i=p;i;i-=lowbit(i))r^=t[i];return r;}
	ll Q(int l,int r){return que(r)^que(l-1);}
}t[21];
vector  e[MAXN];
int n;
ll v[MAXN],val[MAXN],Ans;
bool Sunny;
void Calc(int p,int d)
{
	for(int i=0;i<=20;++i)
	{
		int l=(1<