人均會dsu的賽區..早知道就把陣列開大一點了..
差20分鐘就銀了呀..
最后一場ccpc留下遺憾了...
題目大意：
給出一個樹
讓你求出：
題目思路：
看到lca，那就只能是列舉每個點作為lca的貢獻
所以列舉當前節點作為lca時，所以能夠產生貢獻的就是，他的任意兩棵子樹的貢獻
所以直接列舉當前這個子樹的所有點，然后和之前的權值去匹配
這里需要按位拆分一下：
a^(b+c) != a^b + a^c
但是把數按位拆分之后，對于當前lca權值是ai = c，當前點是ak = a，對于之前所有子樹內權值a^c的點，如果k的第x位是1，那么就看一下a^c的點中 有多少個在第k位是0，反之亦然
這樣就可以把貢獻求出來了
此時就需要一個操作：
求出權值為 c 的第k位 是1的數量
這個地方好像可以用unorder_map 或者 multiset 解決掉
但是比賽時太保險了...加了主席樹..(可能不保險莽一波 就不同結果了)
至于這里的啟發式合并無非就是類似哈夫曼樹的原理:
讓節點個數最大的子樹只訪問一次，但是這里有一個點，如果給出的樹是一條鏈的話，還是會被卡成n^2/2，但是需要注意一個細節點：不可能有ai = ai^aj的情況，因為aj一定大于0
所以此時就可以直接排除鏈的情況把復雜度 總體控制到O(nlogn)
加個主席樹以后總體復雜度：O(nlog^n)
Code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+6;
const int mod = 1e9+7;
const ll base = 1e9;
ll n,m,p;
ll a[maxn];
int L[maxn],R[maxn];
int cnt = 0;
vector<int>v[maxn];
vector< pair<int,int> >g[maxn];
struct node{
int v[22],w;///第k位的數量
int l,r;
}t[maxn*21];
int root[maxn];
int sz[maxn];
int cot = 0;
void Insert(int &x,int y,int l,int r,int pos,ll w){
x = ++cnt;
t[x] = t[y];
for(int i=0;i<=20;i++)
if(w>>i&1) t[x].v[i]++;
t[x].w ++;
if(l == r) return ;
int mid = (l+r)/2;
if(pos<=mid) Insert(t[x].l,t[y].l,l,mid,pos,w);
else Insert(t[x].r,t[y].r,mid+1,r,pos,w);
}
ll Query(int x,int y,int l,int r,int pos,ll w){
if(l == r){
ll ans = 0;
for(int i=0;i<=20;i++){
if(w>>i&1)
ans += ( (t[y].w - t[x].w) - (t[y].v[i]-t[x].v[i]) )*(1<<i);
else
ans += (t[y].v[i] - t[x].v[i])*(1ll<<i);
}
return ans;
}
int mid = (l+r)/2;
if(pos <= mid) return Query(t[x].l,t[y].l,l,mid,pos,w);
return Query(t[x].r,t[y].r,mid+1,r,pos,w);
}
void dfs(int u,int fa){
sz[u] = 1;
for(int e:v[u]){
if(e == fa) continue;
dfs(e,u);
g[u].push_back({sz[e],e});
sz[u] += sz[e];
}
sort(g[u].begin(),g[u].end());
}
void dfs1(int u){
int sz = g[u].size();
L[u] = ++cot;
Insert(root[cot],root[cot-1],0,1e6,a[u],u);
for(int i=sz-1;i>=0;i--){
int e = g[u][i].second;
dfs1(e);
}
R[u] = cot;
}
ll res = 0;
ll work(int u,int R,int L,int x){
ll temp = 0;
if(a[u]^x||a[u]^x<=1e6)
temp += Query(root[L-1],root[R],0,1e6,a[u]^x,u);
for(auto tempx:g[u]) temp += work(tempx.second,R,L,x);
return temp;
}
void dfs2(int u){
int sz = g[u].size();
int pre = L[u],last = R[u];
for(int i=sz-2;i>=0;i--){
last = R[g[u][i+1].second];
res += work(g[u][i].second,last,pre,a[u]);
}
for(int i=sz-1;i>=0;i--) dfs2(g[u][i].second);
}
int main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=1;i<=n-1;i++){
int x,y;scanf("%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1,1);
dfs1(1);
dfs2(1);
printf("%lld\n",res);
return 0;
}
/**
6
4 2 1 6 6 5
1 2
2 3
1 4
4 5
4 6
**/
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/208471.html
標籤：其他