国外网站做淘宝客,小型私人会所装修设计,深圳高端女装品牌,无锡做网站哪家好正题
题目链接:https://www.luogu.com.cn/problem/P3292 题目大意 nnn个点的一棵树#xff0c;每个点都点权。每次询问一条路径#xff0c;选择若干个点的异或和最大。 解题思路
路径上的如何进行计算#xff0c;我们知道我们可以用倍增来计算权值和。我们可以把每个线性基…正题
题目链接:https://www.luogu.com.cn/problem/P3292 题目大意
nnn个点的一棵树每个点都点权。每次询问一条路径选择若干个点的异或和最大。 解题思路
路径上的如何进行计算我们知道我们可以用倍增来计算权值和。我们可以把每个线性基视为边权然后加和就是线性基的合并。
合并线性基时我们将后面的所有did_idi都插入到前面那个线性基中即可。
时间复杂度O((nq)log3n)O((nq)log^3 n)O((nq)log3n) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N21000,T15;
struct node{ll to,next;
}a[N*2];
struct xxj{ll d[80];ll solve(){ll ans0;for(ll i60;i0;i--)if((ans^d[i])ans)ans^d[i];return ans;}void add(ll x){if(!x)return;for(ll i60;i0;i--)if((xi)1ll){if(d[i])x^d[i];else{d[i]x;return;}}}
}w[N][T];
ll n,q,tot,ls[N],dep[N],g[N],f[N][T];
xxj operator(const xxj a,const xxj b){xxj ansa;for(ll i0;i60;i)if(b.d[i])ans.add(b.d[i]);return ans;
}
void addl(ll x,ll y){a[tot].toy;a[tot].nextls[x];ls[x]tot;
}
void dfs(ll x){dep[x]dep[f[x][0]]1;for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yf[x][0])continue;f[y][0]x;dfs(y);}return;
}
void ycl(){for(ll i1;in;i)w[i][0].add(g[i]);for(ll j1;jT;j){for(ll i1;in;i){f[i][j]f[f[i][j-1]][j-1];w[i][j]w[i][j-1]w[f[i][j-1]][j-1];}}return;
}
ll LCA(ll x,ll y){xxj ans;memset(ans.d,0,sizeof(ans.d));if(dep[x]dep[y])swap(x,y);for(ll iT-1;i0;i--)if(dep[f[y][i]]dep[x])ansansw[y][i],yf[y][i];if(xy){ans.add(g[x]);return ans.solve();}for(ll iT-1;i0;i--)if(f[x][i]!f[y][i])ansansw[x][i]w[y][i],xf[x][i],yf[y][i];ansansw[x][0]w[y][0];ans.add(g[f[x][0]]);return ans.solve();
}
int main()
{scanf(%lld%lld,n,q);for(ll i1;in;i)scanf(%lld,g[i]);for(ll i1;in;i){ll x,y;scanf(%lld%lld,x,y);addl(x,y);addl(y,x);}dfs(1);ycl();while(q--){ll x,y;scanf(%lld%lld,x,y);printf(%lld\n,LCA(x,y));}
}
