題目連結:http://acm.hdu.edu.cn/showproblem.php?pid=6430
參考部落格:https://blog.csdn.net/ccsu_cat/article/details/81982389
注意一點就行 線段樹動态開點 向上合并的時候,兩個子樹 周遊然後把其中一個子樹作為父節點就可以。
#include<bits/stdc++.h>
using namespace std;
#define lson o<<1
#define rson o<<1|1
#define MID int m = (l+r)/2;
const int N = +;
int rt[N]= {},ls[N*],rs[N*],sum[N*],sz = ;
vector<int>G[N],fac[N];
void init()
{
for(int i=; i<N; i++)
{
for(int j=i; j<N; j+=i)
{
fac[j].push_back(i);
}
}
}
int cnt = ,ans[N];
void push_up(int o)
{
sum[o] = max(sum[ls[o]],sum[rs[o]]);
}
int p = ;
void update(int k,int l,int r,int &o)
{
if(!o) o = ++cnt;
//p++;
if(l==r)
{
sum[o] = k;
return;
}
int m = (l+r)/;
if(k<=m)update(k,l,m,ls[o]);
else update(k,m+,r,rs[o]);
push_up(o);
}
int Merge(int x1,int x2,int &v)
{
if(!x1||!x2)return x1|x2;
if(sum[x1]==sum[x2])v=max(v,sum[x1]);
if(ls[x1]|ls[x2])ls[x1] = Merge(ls[x1],ls[x2],v);
if(rs[x1]|rs[x2])rs[x1] = Merge(rs[x1],rs[x2],v);
return x1;
}
void dfs(int u)
{
ans[u] =-;
int sz2 = G[u].size();
for(int i=; i<sz2; i++)
{
int v = G[u][i];
dfs(v);
Merge(rt[u],rt[v],ans[u]);
}
}
int main()
{
init();
int n,v;
cin>>n;
for(int i=; i<=n; i++)
{
scanf("%d",&v);
G[v].push_back(i);
}
for(int i=; i<=n; i++)
{
scanf("%d",&v);
int sz2 = fac[v].size();
for(int j=; j<sz2; j++)
{
//cout<<fac[v][j]<<endl;
update(fac[v][j],,sz,rt[i]);
}
}
// cout<<endl<<endl;
//cout<<p<<endl;
dfs();
for(int i=; i<=n; i++)
{
printf("%d\n",ans[i]);
}
return ;
}
//寫代碼時犯了兩個sb錯誤
//1 sz與vector.size()重名了
//2 定義了maxn,周遊數組時又跑到了maxn,數組越界
Other:
每個節點開一個set,然後向上合并
https://blog.csdn.net/liufengwei1/article/details/81983239
題外連結:
樹分塊:
https://blog.csdn.net/Dale_zero/article/details/82227569
組隊賽–套題
https://www.bbsmax.com/A/nAJvAMWGzr