ZigZagK的博客
[Dsu on tree]HDU6430(2018多校训练赛第十场)【TeaTree】题解
[Dsu on tree]HDU6430(2018多校训练赛第十场)【TeaTree】题解
2018年8月22日 20:19
HDU
查看标签

题目概述

给出一棵带点权的树,求每个节点 $i$ 的 $max\{(a_x,a_y)|LCA(x,y)=i,x\not=y\}$ 。

解题报告

因为 $10^5$ 内质因子个数最多只有 $2^7=128$ ,所以可以检查两个不同子树中的节点共有的最大因子。

然后怎么搞?启发式合并?因为不用修改所以可以直接上Dsu on tree。

示例程序

以前Dsu on tree好像写丑了……

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
#include<cstdio> #include<algorithm> using namespace std; const int maxn=100000,maxv=100000,maxd=128; int n,v[maxn+5],D[maxv+5][maxd+5],si[maxn+5],SH[maxn+5],ans[maxn+5]; int E,lnk[maxn+5],nxt[maxn+5],son[maxn+5];int num[maxv+5],MAX;bool vis[maxn+5]; #define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E) void HLD(int x){ for (int j=(si[x]=1,lnk[x]);j;j=nxt[j]){ HLD(son[j]);si[x]+=si[son[j]]; if (si[son[j]]>si[SH[x]]) SH[x]=son[j]; } } void Count(int x){ for (int i=1,V=v[x],si=D[V][0];i<=si;i++) if (num[D[V][i]]) MAX=max(MAX,D[V][i]); for (int j=lnk[x];j;j=nxt[j]) Count(son[j]); } void Insert(int x,int f){ for (int i=1,V=v[x],si=D[V][0];i<=si;i++) num[D[V][i]]+=f; for (int j=lnk[x];j;j=nxt[j]) Insert(son[j],f); } inline void Merge(int x,int f){ MAX=-1;for (int i=1,V=v[x],si=D[V][0];i<=si;i++) if (num[D[V][i]]) MAX=max(MAX,D[V][i]); for (int i=1,V=v[x],si=D[V][0];i<=si;i++) num[D[V][i]]+=f; for (int j=lnk[x];j;j=nxt[j]) if (!vis[son[j]]) Count(son[j]),Insert(son[j],f); } void Solve(int x,bool fl=true){ for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=SH[x]) Solve(son[j],false); if (SH[x]) Solve(SH[x],true),vis[SH[x]]=true;Merge(x,1);ans[x]=MAX; if (SH[x]) vis[SH[x]]=false;if (!fl) Merge(x,-1); } int main(){ freopen("program.in","r",stdin);freopen("program.out","w",stdout); scanf("%d",&n);for (int i=2,x;i<=n;i++) scanf("%d",&x),Add(x,i); for (int i=1;i<=maxv;i++) for (int j=i;j<=maxv;j+=i) D[j][++D[j][0]]=i; for (int i=1;i<=n;i++) scanf("%d",&v[i]);HLD(1);Solve(1); for (int i=1;i<=n;i++) printf("%d\n",ans[i]);return 0; }
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
本文写于 2416 天前,最后更新于 2416 天前。
部分信息可能已经过时,博主也可能已经无法对其内容进行解答。
OK
  1. 1 Skyscape Plum - Melodic Artist
  2. 2 ほしのおとしもの ああああ
  3. 3 感情の摩天楼 ~ Cosmic Mind 上海アリス幻樂団
  4. 4 秘匿されたフォーシーズンズ 上海アリス幻樂団
  5. 5 Ideal and the Real 小西利樹
  6. 6 Undertale Toby Fox
  7. 7 First Steps Lena Raine
  8. 8 Mirror Temple (Mirror Magic Mix) Lena Raine / 2 Mello
  9. 9 City of Tears Christopher Larkin
  10. 10 Tower Of Heaven (You Are Slaves) Feint
Skyscape - Plum - Melodic Artist
00:00 / 00:00
An audio error has occurred, player will skip forward in 2 seconds.

Loading