湛江专业建站联系方式,做idc销售怎样建网站,个人网站建设大全,临沂网站开发公司正题 题目大意
一棵树上每个节点有不同的颜色#xff0c;然后每次询问(x,y,a,b)(x,y,a,b)(x,y,a,b)表示将颜色aaa看为颜色bbb的情况下询问xxx到yyy有多少不种的颜色。 解题思路
数颜色#xff0c;显然树上莫队。我们维护一个欧拉序dfndfndfn(进去时记录一次出来时记录一次)…正题 题目大意
一棵树上每个节点有不同的颜色然后每次询问(x,y,a,b)(x,y,a,b)(x,y,a,b)表示将颜色aaa看为颜色bbb的情况下询问xxx到yyy有多少不种的颜色。 解题思路
数颜色显然树上莫队。我们维护一个欧拉序dfndfndfn(进去时记录一次出来时记录一次)然后rfnirfn_irfni表示点iii进入时在dfndfndfn中的位置rgnirgn_irgni表示点iii在出去时在iii的位置。
然后每次移动端点时只有在[l,r][l,r][l,r]这个区间中出现一次的点的颜色才会被记录入cntcntcnt让出现两次的相互抵消。那么我们就可以让x,yx,yx,y所在它的LCALCALCA的子树中这个序列让他们中间的相互抵消。
不过要注意若x,yx,yx,y不是他们的LCALCALCA那么他们的LCALCALCA就被计算了两次就重复了统计答案时要减去重复的。 codecodecode
#includecstdio
#includealgorithm
#includequeue
#includecmath
using namespace std;
const int N51000,M110000;
struct line{int to,next,w;
}a[M];
struct Que_node{int l,r,a,b,id,pos;
}que[M];
bool operator(Que_node x,Que_node y)
{return x.posy.pos?x.ry.r:x.posy.pos;}
int n,m,c[N],dfn[M],rfn[N],rgn[N],v[N],cnt,num,ans[N];
int tot,x,y,ls[N],dep[N],f[N][30],t,T;
bool b[N];
queueint q;
inline int read()
{int X0,w0; char c0;while(c0||c9) {w|c-;cgetchar();}while(c0c9) X(X3)(X1)(c^48),cgetchar();return w?-X:X;
}
inline void addl(int x,int y,int w)
{a[tot].toy;a[tot].nextls[x];a[tot].ww;ls[x]tot;
}
void dfs(int x,int fa)
{dfn[cnt]x;rfn[x]cnt;for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa) continue;dfs(y,x);}dfn[cnt]x;rgn[x]cnt;
}
inline void bfs(int s)
{q.push(s);dep[s]1;while(!q.empty()){int xq.front();q.pop();for (int ils[x];i;ia[i].next){int ya[i].to;if (dep[y]) continue;q.push(y);f[y][0]x;dep[y]dep[x]1;}}T(int)(log(n)/log(2))1;for (int j1;jT;j)for (int i1;in;i)f[i][j]f[f[i][j-1]][j-1];
}
inline int LCA(int x,int y)
{if (dep[x]dep[y]) swap(x,y);for (int iT;i0;i--)if (dep[f[y][i]]dep[x]) yf[y][i];if (xy) return x;for (int iT;i0;i--)if (f[y][i]!f[x][i]) {xf[x][i];yf[y][i];}return f[x][0];
}
void rev(int x)
{if(b[x]) v[c[x]]--,num-(v[c[x]]0);else num(v[c[x]]0),v[c[x]];b[x]^1;
}
void Keep_zzy(int l,int r,int L,int R)
{while(lL) rev(dfn[l]),l;while(lL) l--,rev(dfn[l]);while(rR) r,rev(dfn[r]);while(rR) rev(dfn[r]),r--;
}
int main()
{freopen(apple.in,r,stdin);freopen(apple.out,w,stdout);nread();mread();for(int i1;in;i)c[i]read();for(int i1;in;i){addl(xread(),yread(),1);addl(y,x,1);}dfs(0,0);bfs(0);t(int)sqrt((double)cnt);for(int i1;im;i){scanf(%d%d%d%d,que[i].l,que[i].r,que[i].a,que[i].b);if(rfn[que[i].l]rfn[que[i].r])swap(que[i].l,que[i].r);que[i].lrgn[que[i].l];que[i].rrfn[que[i].r];if(que[i].lque[i].r) que[i].lrfn[dfn[que[i].l]];que[i].idi;que[i].pos(que[i].l-1)/t1;}sort(que1,que1m);int l1,r0;v[0]1; for(int i1;im;i){int xque[i].l,yque[i].r;Keep_zzy(l,r,x,y);int lcaLCA(dfn[x],dfn[y]);bool flag0;if(dfn[x]!lcadfn[y]!lca)rev(lca),flag1;ans[que[i].id]num;if(v[que[i].a]v[que[i].b]que[i].a!que[i].b)ans[que[i].id]--;if(flag) rev(lca);}for(int i1;im;i)printf(%d\n,ans[i]);
}
