平面网站设计,wordpress数据表更换域名,网络外包公司,旅游网站设计报告正题
题目链接:https://www.luogu.com.cn/problem/P6177 题目大意 nnn个点的一棵树mmm次询问树上颜色。 强制在线 1≤n≤4105,1≤m≤105,0≤vali2311\leq n\leq 4\times 10^5,1\leq m\leq 10^5,0\leq val_i2^{31}1≤n≤4105,1≤m≤105,0≤vali231 解题思路
把所…正题
题目链接:https://www.luogu.com.cn/problem/P6177 题目大意
nnn个点的一棵树mmm次询问树上颜色。 强制在线
1≤n≤4×105,1≤m≤105,0≤vali2311\leq n\leq 4\times 10^5,1\leq m\leq 10^5,0\leq val_i2^{31}1≤n≤4×105,1≤m≤105,0≤vali231 解题思路
把所有深度为n\sqrt nn并且下面至少有n\sqrt nn的深度的点标记这样保证关键点数量不超过n\sqrt nn。
然后每个点到他周围关键点的距离也不会超过 n\sqrt nn 。
这样可以处理出关键点两两之间的颜色bitsetbitsetbitset然后每次路径找两个最近的关键点爆做就好了。
时间复杂度O((mn)(nnω))O((mn)(\sqrt n\frac{n}{\omega}))O((mn)(nωn)) code
#includecstdio
#includecstring
#includealgorithm
#includebitset
#includecmath
using namespace std;
const int N41000,T300,M(4e4)/T10;
struct node{int to,next;
}a[N1];
int n,m,tot,cnt,sum,fa[N],v[N],top[N],ls[N],d[N],dep[N],w[N],b[N],mark[N],dfn[N],ed[N],g[M][M];
bitsetN f[M][M],bt;
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs(int x){for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa[x])continue;dep[y]dep[x]1;fa[y]x;dfs(y);d[x]max(d[x],d[y]1);}if(dep[x]%T0d[x]T)mark[x]cnt;return;
}
void dFs(int x){if(mark[x])top[x]x;dfn[x]cnt;for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa[x])continue;top[y]top[x];dFs(y);}ed[x]cnt;return;
}
void calc(int x,int p,int fa){if(!v[w[x]])bt[w[x]]1,sum;v[w[x]];if(mark[x])f[p][mark[x]]bt,g[p][mark[x]]sum;for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa)continue;calc(y,p,x);}v[w[x]]--;if(!v[w[x]])bt[w[x]]0,sum--;return;
}
int main()
{scanf(%d%d,n,m);for(int i1;in;i)scanf(%d,w[i]),b[i]w[i];sort(b1,b1n);int Lunique(b1,b1n)-b-1;for(int i1;in;i)w[i]lower_bound(b1,b1L,w[i])-b;for(int i1;in;i){int x,y;scanf(%d%d,x,y);addl(x,y);addl(y,x);}dfs(1);cnt0;dFs(1);for(int i1;in;i)if(mark[i])calc(i,mark[i],i);int last0;while(m--){int x,y;scanf(%d%d,x,y);x^last;if(top[x]top[y]){int xxx,yyy,ans0;while(x!y){if(dep[x]dep[y])swap(x,y);if(!v[w[x]])ans,v[w[x]]1;xfa[x];}if(!v[w[x]])ans,v[w[x]]1;printf(%d\n,ans);lastans;xxx;yyy;while(x!y){if(dep[x]dep[y])swap(x,y);v[w[x]]0;xfa[x];}v[w[x]]0;}else{if(dfn[x]dfn[y]dfn[x]ed[y])swap(x,y);if(dfn[y]dfn[x]dfn[y]ed[x]){int ztop[y];while(top[fa[z]]!top[x])ztop[fa[z]];btf[mark[z]][mark[top[y]]];int ansg[mark[z]][mark[top[y]]];while(y!top[y]){if(!bt[w[y]])ans,bt[w[y]]1;yfa[y];}while(z!x){if(!bt[w[z]])ans,bt[w[z]]1;zfa[z];}if(!bt[w[z]])ans,bt[w[z]]1;printf(%d\n,ans);lastans;}else{btf[mark[top[x]]][mark[top[y]]];int ansg[mark[top[x]]][mark[top[y]]];while(x!top[x]){if(!bt[w[x]])ans,bt[w[x]]1;xfa[x];}while(y!top[y]){if(!bt[w[y]])ans,bt[w[y]]1;yfa[y];}printf(%d\n,ans);lastans;}}}return 0;
}
