百度秒收网站,seo关键词优化软件合作,网页设计步骤及方法,建设学校网站的作用文章目录解析update:代码所谓树上莫队#xff0c;就是在树上的莫队 #xff08;逃#xff09; 传送门
解析
似乎就是树上的这道题 考虑如何转化为序列问题呢? 考虑dfs序 但是又一个问题。。。 似乎这条链的dfs序不连续啊 树剖一下就好啦 考虑更阳间的方法 求出这棵树的欧…
文章目录解析update:代码所谓树上莫队就是在树上的莫队 逃 传送门
解析
似乎就是树上的这道题 考虑如何转化为序列问题呢? 考虑dfs序 但是又一个问题。。。 似乎这条链的dfs序不连续啊 树剖一下就好啦 考虑更阳间的方法 求出这棵树的欧拉序在这个欧拉序上询问 那么我们发现这样的话其实会多算的部分就都会多算2遍 比如样例
以1为根欧拉序为 13442231 那么我们考虑4-3 对应的序列就是 44223 不在路径上的2恰好算了2次 所以我们可以利用异或的性质 还有一些特判的问题
lca不在端点时需要额外计算lca左端点不时lca时需要额外计算左端点 画画图就很清楚了
update:
上面那个特判是洛谷野生题解的有点过于阴间了… ybt的实现优美的多至少易于记忆 设一个点进入和离开dfs的时间分别为 in(x),out(x)in(x),out(x)in(x),out(x)。 令 in(x)in(y)in(x)in(y)in(x)in(y)分情况讨论
xxx 是 yyy 的祖先那么答案就是 [in(x),in(y)][in(x),in(y)][in(x),in(y)]。xxx 不是 yyy 的祖先那么在 [out(x),in(y)][out(x),in(y)][out(x),in(y)] 的基础上还要加上 lca(x,y)lca(x,y)lca(x,y)。
代码
#includebits/stdc.h
using namespace std;
#define ll long long
const int N3e5100;
const int M1050;
const int mod998244353;
const double eps1e-6;
ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-) f-1;cgetchar();}while(isdigit(c)){xx*10c-0;cgetchar();}return x*f;
}
int n,m;
struct node{int to,nxt;
}p[N1];
int fi[N],cnt;
void addline(int x,int y){p[cnt](node){y,fi[x]};fi[x]cnt;
}
int pl[N][22],dep[N],siz[N];
ll v[N],w[N];
int pos[N],dfn[N],ed[N],Tim;
void dfs(int x,int f){pl[x][0]f;pos[x]Tim;dfn[Tim]x;siz[x]1;for(int k1;k18;k) pl[x][k]pl[pl[x][k-1]][k-1];for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(tof) continue;dep[to]dep[x]1;dfs(to,x);siz[x]siz[to];}dfn[Tim]x;ed[x]Tim;
}
bool vis[N];
int a[N],tim,tot,from[N],to[N],id[N],bel[N];
int Lca(int x,int y){if(dep[x]dep[y]) swap(x,y);for(int k18;k0;k--){if(!pl[x][k]||dep[pl[x][k]]dep[y]) continue;xpl[x][k];}
// printf(LCA:x%d y%d ,x,y);if(xy){
// printf(ares%d\n,x);return x;}
// printf( mid:x%d y%d ,x,y);for(int k18;k0;k--){if(pl[x][k]pl[y][k]) continue;xpl[x][k];ypl[y][k];}
// printf(x%d res%d\n,x,pl[x][0]);return pl[x][0];
}
struct query{int l,r,t,id,lca;bool operator (const query o)const{if(bel[l]!bel[o.l]) return bel[l]bel[o.l];else if(bel[r]!bel[o.r]) return bel[r]bel[o.r];else return to.t;}
}ask[N];
int l,r,t,bac[N];
ll now;
ll ans[N];
inline void work(int x){xdfn[x];(vis[x]^1)?nowv[a[x]]*w[bac[a[x]]]:now-v[a[x]]*w[bac[a[x]]--];
}
int q;
int ww;
int main(){memset(fi,-1,sizeof(fi));cnt-1;nread();mread();qread();for(int i1;im;i) v[i]read();for(int i1;in;i) w[i]read();for(int i1;in;i){int xread(),yread();addline(x,y);addline(y,x);}for(int i1;in;i) a[i]read();dep[1]1;dfs(1,0);
// for(int i1;iTim;i) printf(%d ,dfn[i]);
// printf(\n);wwfloor(pow(Tim,2.0/3));for(int i1;iTim;i){bel[i](i-1)/ww1;}for(int i1;iq;i){int opread(),xread(),yread();if(op0){tim;int ox;from[tim]a[o];id[tim]o;a[o]y;to[tim]a[o];}else{if(pos[x]pos[y]) swap(x,y);ask[tot](query){pos[x],pos[y],tim,tot,pos[Lca(x,y)]};}
// printf(i%d op%d x%d y%d\n,i,op,x,y);}sort(ask1,ask1tot);l1;ttim;for(int i1;itot;i){int nlask[i].l,nrask[i].r,ntask[i].t,lcaask[i].lca;while(lnl) work(l);while(lnl) work(--l);while(rnr) work(r);while(rnr) work(r--);while(tnt){t;int oid[t],f0;if((pos[o]lled[o]ed[o]r)) f1;else if(lpos[o]pos[o]rred[o]) f2;if(f1) work(ed[o]);else if(f2) work(pos[o]);a[o]to[t];if(f1) work(ed[o]);else if(f2) work(pos[o]);}while(tnt){int oid[t],f0;if((pos[o]lled[o]ed[o]r)) f1;else if(lpos[o]pos[o]rred[o]) f2;if(f1) work(ed[o]);else if(f2) work(pos[o]);a[o]from[t];if(f1) work(ed[o]);else if(f2) work(pos[o]);t--;}if(nl!lca){work(nl);if(nr!lca) work(lca);}
// printf(id%d (%d %d %d %d) res%lld\n,ask[i].id,nl,nr,nt,lca,now);ans[ask[i].id]now;if(nl!lca){work(nl);if(nr!lca) work(lca);}}for(int i1;itot;i) printf(%lld\n,ans[i]);return 0;
}
/**/
