公司做网站费会计科目,忻州建设网站的公司,做企业网站首页尺寸,烟台城乡建设局官方信息网站正题
题目链接:https://gmoj.net/senior/#main/show/5097 题目大意 nnn个点的一棵树#xff0c;每个节点有权值。对于每个点求树上所有权值去除掉他的子树的权值后的mexmexmex值。 解题思路
对于一个权值www#xff0c;权值为www的所有点的LCALCALCA到根节点的路径上都不会…正题
题目链接:https://gmoj.net/senior/#main/show/5097 题目大意
nnn个点的一棵树每个节点有权值。对于每个点求树上所有权值去除掉他的子树的权值后的mexmexmex值。 解题思路
对于一个权值www权值为www的所有点的LCALCALCA到根节点的路径上都不会包括www这个权值。
我们从小到大枚举权值将这些路径上用www覆盖答案覆盖过的位置不再覆盖用一个并查集维护覆盖过的集合即可并查集的头部指向集合中最顶部的节点即可。
时间复杂度O(nlogn)O(n\log n)O(nlogn) codecodecode
#includecstdio
#includecstring
#includealgorithm
#includecctype
using namespace std;
const int N1e610;
struct node{int to,next;
}a[N1];
int T,n,m,tot,ls[N],w[N],siz[N],f[N],v[N];
int fa[N],son[N],top[N],dep[N],ans[N];
int read(){int x0,f1;char cgetchar();while(!isdigit(c)){if(c-)f-f;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}
void print(int x)
{if(x9)print(x/10);putchar(x%100);return;}
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs1(int x){dep[x]dep[fa[x]]1;siz[x]1;for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa[x])continue;fa[y]x;dfs1(y);siz[x]siz[y];if(siz[y]siz[son[x]])son[x]y;}return;
}
void dfs2(int x){if(son[x]){top[son[x]]top[x];dfs2(son[x]);}for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa[x]||yson[x])continue;top[y]y;dfs2(y);}return;
}
int LCA(int x,int y){while(top[x]!top[y]){if(dep[top[x]]dep[top[y]])swap(x,y);xfa[top[x]];}return (dep[x]dep[y])?x:y;
}
int find(int x)
{return (f[x]x)?x:(f[x]find(f[x]));}
int main()
{freopen(game.in,r,stdin);freopen(game.out,w,stdout);scanf(%d,T);while(T--){nread();mread();totv[0]0;for(int i1;in;i){w[i]read();f[i]i;ls[i]v[i]ans[i]son[i]fa[i]0;}for(int i1;in;i){int xread(),yread();addl(x,y);addl(y,x);}top[1]1;dfs1(1);dfs2(1);for(int i1;in;i){if(w[i]n)continue;if(!v[w[i]])v[w[i]]i;else v[w[i]]LCA(v[w[i]],i);}int p0;for(;v[p];p){int xfind(v[p]);while(x){ans[x]p1;f[x]fa[x];xfind(x);}}for(int i1;in;i)print(ans[i]?(ans[i]-1):p),putchar( );putchar(\n);}return 0;
}
