给定一颗2e5个节点的数,每个节点有一个权值(2e5),输出每个节点的beauty. 一个节点的beauty定义为它到原点路径上的各个点中删去一个点后权值的gcd. 每个点独立考虑,原点的beauty就是它的权值.
参考的一种方法如下:拿一种数据结构储存每个点的所有可能情况,居然不会超时? 真如艾教所说,大胆写暴力. 每个点的pri表示权值,gcd表示从根到它所有点的gcd , set p表示它的所有情况(删去一个点后的gcd),ans表示p中的最大值,即结果. 转移时: nex.gcd=__gcd(x.gcd,nex.pri); nex.p[i]=__gcd(x.p[i],nex.pri);此外把x.gcd也加入nex.p中,表示删去新加入的点. 记得对原点特判一下即可.
#include <bits/stdc++.h> using namespace std; #define M 200010 /*记得修改*/ struct Item { /*添加属性,如点权等*/ int pri; int gcd; //未删去值的gcd set<int,greater<int>> p; //父节点所有可能的删去值的情况 int ans; //结果,即p的最大元素 /**/ set<int> edge; } item[M]; void dfs() { stack<int> s; s.push(1); /*对根节点访问*/ item[1].gcd=item[1].pri; item[1].p.insert(0); item[1].ans=item[1].pri; /**/ while(!s.empty()) { int x = s.top(); s.pop(); for(auto nex : item[x].edge) { /*对子节点访问*/ item[nex].gcd=__gcd(item[x].gcd,item[nex].pri); for(auto idx:item[x].p) { item[nex].p.insert(__gcd(idx,item[nex].pri)); } item[nex].p.insert(item[x].gcd); item[nex].ans=*item[nex].p.begin(); /**/ item[nex].edge.erase(x); s.push(nex); } } } int main(void) { int n; scanf("%d", &n); /*可读入点权*/ for(int i = 1; i <= n; i++) scanf("%d", &item[i].pri); for(int i = 0; i < n - 1; i++) { int ti, tj; scanf("%d%d", &ti, &tj); /*可读入边权,需要将set<int>改为set<pii>*/ item[ti].edge.insert(tj); item[tj].edge.insert(ti); } dfs(); for(int i=1;i<n;i++) { printf("%d ",item[i].ans ); } printf("%d\n",item[n].ans ); return 0; }使用了新写的tree模板,代码用时15分钟.
不超时的原因可能是,p里真正并不会储存很多数据,很多都重复了. 这个题的总结是:要学会简化问题. 比如这个题实际上和一条链的解法一点区别都没有,只不过借用了树的形态. 甚至可以看成一个数列依次求beauty,这样可以大幅度简化问题.
