山东公路建设集团网站,网站开发需要那些技能,滨海做网站哪家公司好,initial wordpress解析
虽然使用三个log的倍增算法艹过去了 但是我们还是来聊聊正解吧
考虑点分治 对于当前的根#xff0c;dfs求出联通块内每个点到当前根的线性基 一条路径的答案应该在路径出现上第一个成为根的点时统计到 具体来说#xff0c;就是路径的两端点在同一个solve函数的不同子树…解析
虽然使用三个log的倍增算法艹过去了 但是我们还是来聊聊正解吧
考虑点分治 对于当前的根dfs求出联通块内每个点到当前根的线性基 一条路径的答案应该在路径出现上第一个成为根的点时统计到 具体来说就是路径的两端点在同一个solve函数的不同子树内 通过奇怪的时间戳标记可以实现 对于询问每个结点开个vector暴力遍历即可 由于每个结点最多被dfslog遍所以复杂度是对的 复杂度瓶颈在dfs求线性基上时间复杂度nlog2nnlog^2nnlog2n 然后就ok啦 但是懒得再写一遍了所以还是贴的3log代码
代码
#includebits/stdc.h
using namespace std;
#define ll long long
#define inf (n1)
//#define debug(...) fprintf(stderr,__VA_ARGS__)
const int N2e4100;
const int M2e510500;
const double eps1e-5;
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}int n,m;struct node{int to,nxt;
}p[N1];
int fi[N],cnt;
inline void addline(int x,int y){p[cnt](node){y,fi[x]};fi[x]cnt;return;
}ll mi[65];struct basic{ll v[62];basic(){memset(v,0,sizeof(v));}void upd(ll x){for(int i60;i0;i--){if(xmi[i]){if(!v[i]){v[i]x;break;}else x^v[i];}}}
}b[N][16];
inline void merge(basic v1,basic v2){for(int i0;i60;i){if(v2.v[i]) v1.upd(v2.v[i]);}return;
}ll val[N];
int pl[N][16],dep[N];
void dfs(int x,int f){b[x][0].upd(val[f]);pl[x][0]f;for(int k1;pl[x][k-1];k){pl[x][k]pl[pl[x][k-1]][k-1];b[x][k]b[x][k-1];merge(b[x][k],b[pl[x][k-1]][k-1]);}dep[x]dep[f]1;for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(tof) continue;dfs(to,x);}return;
}
basic res;
ll query(int x,int y){memset(res.v,0,sizeof(res.v));res.upd(val[x]);res.upd(val[y]);if(dep[x]dep[y]) swap(x,y);for(int k15;k0;k--){if(dep[x]-mi[k]dep[y]) continue;merge(res,b[x][k]);xpl[x][k];}if(x!y){for(int k15;k0;k--){if(pl[x][k]pl[y][k]) continue;merge(res,b[x][k]);merge(res,b[y][k]);xpl[x][k];ypl[y][k];}res.upd(val[pl[x][0]]);}ll ans(0);for(int i60;i0;i--){//if(res.v[i]) printf(i%d v%lld\n,i,res.v[i]);if(!res.v[i]||(ansmi[i])) continue;ans^res.v[i];//printf( ans%lld\n,ans);}//putchar(\n);return ans;
}
int main(){
#ifndef ONLINE_JUDGE//freopen(a.in,r,stdin);//freopen(a.out,w,stdout);
#endifmemset(fi,-1,sizeof(fi));cnt-1;mi[0]1;for(int i1;i60;i) mi[i](mi[i-1]1);nread();mread();for(int i1;in;i) val[i]read();for(int i1;in;i){int xread(),yread();addline(x,y);addline(y,x);}dfs(1,0);for(int i1;im;i){int xread(),yread();printf(%lld\n,query(x,y));}return 0;
}
/*
*/
