培训建设网站,电商设计师的工作内容,泉州关键词优化报价,wordpress 遍历用户正题
题目链接:https://www.luogu.com.cn/problem/P5311 题目大意
给出nnn个点的一棵树#xff0c;每个节点有一个颜色#xff0c;mmm次询问提出区间[l,r][l,r][l,r]的点构成的生成子图中xxx所在连通块的颜色数。 1≤n,m,ai≤1051\leq n,m,a_i\leq 10^51≤n,m,ai≤105 解…正题
题目链接:https://www.luogu.com.cn/problem/P5311 题目大意
给出nnn个点的一棵树每个节点有一个颜色mmm次询问提出区间[l,r][l,r][l,r]的点构成的生成子图中xxx所在连通块的颜色数。
1≤n,m,ai≤1051\leq n,m,a_i\leq 10^51≤n,m,ai≤105 解题思路
用点分树解决本题是很妙的想法。/bx
考虑点分树如何解决对于一个询问l,r,xl,r,xl,r,x如果xxx在点分树上的一个祖先yyy满足xxx到yyy的路径都是[l,r][l,r][l,r]的点那么此时在yyy的点分子树上的所有节点zzz都满足如果yyy到zzz的路径都是[l,r][l,r][l,r]的节点那么xxx到zzz的也是。具体原因很好理解因为两条路径重复的那一段路已经满足条件了。
那么我们此时就可以将一个条件拆分成两个条件挂在yyy上了具体地我们对于每个询问找到xxx点分树上深度最小的祖先yyy满足xxx到yyy的路径上都是[l,r][l,r][l,r]的节点然后把这个询问挂在这个点上。
然后我们暴力枚举所有点然后处理它的点分树子树假设现在枚举到xxx点我们把它的所有儿子按照xxx到它们的路径上的最小值从大到小询问然后挂在xxx点上的询问按照lll从大到小排序。
然后暴力遍历记录每个颜色最小的mxmxmx表示yyy到这个颜色的点需要经过的路径最大值然后把权值丢到树状数组上查询即可。
时间复杂度O(nlog2n)O(n\log^2 n)O(nlog2n) code
#includecstdio
#includecstring
#includealgorithm
#includevector
#define lowbit(x) (x-x)
using namespace std;
const int N1e510;
struct edge{int to,next;
}a[N1];
struct node{int x,fa,l,r;
};
int n,m,tot,num,root,ls[N],c[N];
int siz[N],f[N],t[N],lat[N],ans[N];
vectornode anc[N],son[N],q[N];
bool v[N];
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void Groot(int x,int fa){siz[x]1;f[x]0;for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa||v[y])continue;Groot(y,x);siz[x]siz[y];f[x]max(f[x],siz[y]);}f[x]max(f[x],num-siz[x]);if(f[x]f[root])rootx;return;
}
void dfs(int x,int fa,int fr,int mi1e9,int mx-1e9){mimin(x,mi);mxmax(x,mx);anc[x].push_back((node){x,fr,mi,mx});son[fr].push_back((node){x,fr,mi,mx});for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa||v[y])continue;dfs(y,x,fr,mi,mx);}return;
}
void Build(int x){int Snum;v[x]1;dfs(x,0,x);for(int ils[x];i;ia[i].next){int ya[i].to;if(v[y])continue;num(siz[y]siz[x])?(S-siz[x]):siz[y];root0;Groot(y,x);Build(root);}return;
}
bool cmp(node x,node y)
{return x.ly.l;}
void Change(int x,int val){while(xn){t[x]val;xlowbit(x);}return;
}
int Ask(int x){int ans0;while(x){anst[x];x-lowbit(x);}return ans;
}
int main()
{scanf(%d%d,n,m);for(int i1;in;i)scanf(%d,c[i]);for(int i1;in;i){int x,y;xi,yi1;scanf(%d%d,x,y);addl(x,y);addl(y,x);}f[0]n1;numn;Groot(1,1);Build(root);for(int t1;tm;t){int l,r,x;scanf(%d%d%d,l,r,x);for(int i0;ianc[x].size();i)if(anc[x][i].llanc[x][i].rr){q[anc[x][i].fa].push_back((node){x,t,l,r});break;}}for(int i0;iN;i)lat[i]n1;for(int p1;pn;p){sort(q[p].begin(),q[p].end(),cmp);sort(son[p].begin(),son[p].end(),cmp);int z0;for(int i0;ison[p].size();i){node xson[p][i];while(zq[p].size()q[p][z].lx.l){node yq[p][z];ans[y.fa]Ask(y.r);z;}Change(lat[c[x.x]],-1);lat[c[x.x]]min(lat[c[x.x]],x.r);Change(lat[c[x.x]],1);}while(zq[p].size()){node yq[p][z];ans[y.fa]Ask(y.r);z;}for(int i0;ison[p].size();i){node xson[p][i];Change(lat[c[x.x]],-1);lat[c[x.x]]n1;}}for(int i1;im;i)printf(%d\n,ans[i]);return 0;
}
