坪山网站建设基本流程,游戏网页在线玩,上海建站模板系统,网站代运营要多少费用吗正题
题目链接:https://www.luogu.com.cn/problem/P6118 题目大意
给出一棵nnn个点的树#xff0c;对于一个点xxx来说#xff0c;独特的点y(y≠x)y(y\neq x)y(yx)是指不存在zzz使得dis(y,x)dis(z,x)dis(y,x)dis(z,x)dis(y,x)dis(z,x)#xff0c;其中x≠z,y≠zx\neq z,…正题
题目链接:https://www.luogu.com.cn/problem/P6118 题目大意
给出一棵nnn个点的树对于一个点xxx来说独特的点y(y≠x)y(y\neq x)y(yx)是指不存在zzz使得dis(y,x)dis(z,x)dis(y,x)dis(z,x)dis(y,x)dis(z,x)其中x≠z,y≠zx\neq z,y\neq zxz,yz。
每个点有个颜色对于每个点xxx求对于它来说独特的点所包含的颜色种类数。
1≤n≤2×1051\leq n\leq 2\times 10^51≤n≤2×105 解题思路
首先我们很容易得到一个结论就是记距离xxx最远的点是yyy那么对于点xxx独特的点肯定都在x↔yx\leftrightarrow yx↔y的路径上。证明很简单因为不在这个上面的肯定能在这条路径上找到一个点和它深度相等
然后树上有一个性质就是距离任意点xxx最远的点yyy肯定在树的直径的某一端。
那么我们现在考虑对于一个点xxx快速求出所有其他点yyy路径x→yx\rightarrow yx→y上点的贡献。
我们考虑用一个东西去存目前x→yx\rightarrow yx→y路径上的节点集合SSS然后对于每个点预处理出一个子树深度最深的儿子和次深的儿子。
然后如果我们不是往最深那个儿子那里走记它的深度为depdepdep那么集合SSS中距离xxx超过dep1dep1dep1的点都不会产生贡献。
如果是往最深那个走那么就是次深那个节点的深度。
我们考虑直接用一个栈来维护这个集合SSS然后每次先往最深的那个儿子走再走其他的儿子实时弹出集合SSS中的节点。
但是这样我们回溯的时候是不是需要把之前弹出来的节点还回去呢能够惊喜的发现继续往回到分叉的时候这些节点依旧要被弹出因为刚刚走过的子树有这些深度的节点。
所以这样每个点就最多被弹出一次了。
时间复杂度O(n)O(n)O(n) code
#includecstdio
#includecstring
#includealgorithm
#includestack
using namespace std;
const int N2e510;
struct node{int to,next;
}a[N1];
int n,m,tot,sum,root,mx,ls[N],col[N],ans[N];
int son[N],ton[N],len[N],c[N],dep[N],las[N];
stackint s,tmp[N];
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs(int x,int fa,int dep){if(depmx){mxdep;rootx;}for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa)continue;dfs(y,x,dep1);}return;
}
void ins(int x)
{sum(!c[col[x]]);c[col[x]];return;}
void del(int x)
{c[col[x]]--;sum-(!c[col[x]]);return;}
void calc(int x,int fa){len[x]son[x]ton[x]0;for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa)continue;dep[y]dep[x]1;calc(y,x);len[x]max(len[x],len[y]1);if(len[y]len[son[x]])ton[x]son[x],son[x]y;else if(len[y]len[ton[x]])ton[x]y;}return;
}
void sets(int x,int len){while(!s.empty()dep[x]-dep[s.top()]len)del(s.top()),s.pop();return;
}
void solve(int x,int fa){sets(x,len[ton[x]]1);s.push(x);ins(x);if(son[x])solve(son[x],x);if(!son[son[x]])s.pop(),del(x);sets(x,len[son[x]]1);if(dep[x]las[x])ans[x]sum,las[x]dep[x];for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa||yson[x])continue;s.push(x);ins(x);solve(y,x);if(!son[y])s.pop(),del(x);}return;
}
int main()
{scanf(%d%d,n,m);len[0]-1;for(int i1,x,y;in;i){scanf(%d%d,x,y);addl(x,y);addl(y,x);}for(int i1;in;i)scanf(%d,col[i]);dfs(1,0,1);calc(root,0);solve(root,0);mx0;dfs(root,0,1);dep[root]0;calc(root,0);solve(root,0);for(int i1;in;i)printf(%d\n,ans[i]);return 0;
}
