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

2024杭电多校01——1003树

news 来源：原创 2024/9/20 7:45:59

补题链接
在这里插入图片描述
官方题解

补充:
$(\sum_{u \in tree_i} a_u)^2$ $\sum_{u \in tree_i} a_u^{2}+2\sum_{x \in tree_i,y \in tree_i} a_x*a_y$
可以用树状数组算出 $\sum a_u^{2}$ 和 $\sum a_u$ ,这样通过上述式子就可以求出 $\sum a_x*a_y$ 即原文中的第二行

蒟蒻不太理解后面说的话，只能讲点自己会的,对于一个集合和一个加入的点,会有大于集合元素的贡献和小于集合元素的贡献(贡献就是f(u,v)要我们求和的东西)，如何快速求出贡献，可以用三个树状数组去维护，t1代表小于等于x的元素个数,tx代表所有元素的和，txx代表大于x的元素平方和

每次合并答案的时候, $\sum f(u,v) = \sum_{a[u] \leq a[x]} f(x,u) +\sum_{a[x] \leq a[v} f(x,v)$ 小于等于x的元素个数存储在t1里，大于x的元素的平方和存储在txx里,要减去的部分全在tx里,这样就可以跑树上启发式合并了

#include<bits/stdc++.h>
using namespace std;
using i64 = unsigned long long;
using i128 = __int128;
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int unsigned long long
const int maxn = 1e6+10;
int n,a[maxn];
vector<int>g[maxn];int son[maxn],siz[maxn],HH;
int f[maxn],ff[maxn],l[maxn],r[maxn],idx=1;void dfs(int x,int fa){siz[x]=1;f[x]=idx;ff[idx] = x;l[x]=idx++;for(auto y:g[x]){if(y==fa) continue;dfs(y,x);siz[x]+=siz[y];if(siz[son[x]]<siz[y]) son[x] = y;}r[x] = idx-1;
}struct bit{i64 tree[maxn];inline int lowbit(int x){return x&(-x);}inline void update(int x,i64 v){for(int i = x;i<maxn;i+=lowbit(i)){tree[i]+=v;}}inline i64 query(int x){i64 res = 0;for(int i = x;i>0;i-=lowbit(i)){res+=tree[i];}return res;}
}t1,tx,txx;i64 add(i64 x){return x*x*t1.query(x)-x*tx.query(maxn-10)+txx.query(maxn-10)-txx.query(max(x,0uLL));
}vector<i64> tmp;
void upd(i64 x){t1.update(x,1uLL);tx.update(x,x);txx.update(x,x*x);tmp.push_back(x);
}void clear(){for(auto x:tmp){t1.update(x,-1);tx.update(x,-1uLL*x);txx.update(x,-1uLL*x*x);}vector<i64>().swap(tmp);//清空tmp省内存
}i64 ans[maxn];
void dsu(int x,int fa,bool op){for(auto y:g[x]){if(y==fa||y==son[x]) continue;dsu(y,x,0);}if(son[x]) dsu(son[x],x,1),HH = son[x],ans[x] = ans[son[x]];for(auto y:g[x]){if(y==fa||y==HH) continue;ans[x]+=ans[y];for(int i = l[y];i<=r[y];++i){ans[x]+=2uLL*add(a[ff[i]]);}for(int i = l[y];i<=r[y];++i){upd(a[ff[i]]);}}ans[x]+=2uLL*add(a[x]);HH=0;if(!op) clear();else upd(a[x]);
}signed main(){ios;cin>>n;for(int i = 1;i<n;++i){int x,y;cin>>x>>y;g[x].push_back(y);g[y].push_back(x);}for(int i = 1;i<=n;++i) cin>>a[i];dfs(1,0);dsu(1,0,1);i64 res = 0;for(int i = 1;i<=n;++i) res=(res^ans[i]);cout<<res<<"\n";return 0;
}