HDU - 6430 TeaTree
제목 링크: HDU - 6430
수제.
분명히 한 숫자의 인자는 그리 많지 않을 것이다.폭력은 모든 숫자의 인자를 구하고 서브 트리 라인에서 트리를 합치면 된다.합병할 때마다 답안을 업데이트합니다.
AC 코드:
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include
//#define int long long
using namespace std;
const int N=1e5+10,M=N*400;
int n,up,rt[N],lc[M],rc[M],sum[M],res[N],a[N],cnt,flag;
vector<int> g[N],v[N];
void get(int n){for(int i=1;i<=n;i++) for(int j=i;j<=n;j+=i) v[j].push_back(i);}
void change(int &p,int l,int r,int x){
if(!p) p=++cnt;
if(l==r){sum[p]++; return ;} int mid=l+r>>1;
if(x<=mid) change(lc[p],l,mid,x);
else change(rc[p],mid+1,r,x);
}
int merge(int x,int y,int l,int r){
if(!x||!y) return x+y;
if(l==r){if(sum[x]&&sum[y]) res[flag]=max(res[flag],l); sum[x]+=sum[y]; return x;}
int mid=l+r>>1;
lc[x]=merge(lc[x],lc[y],l,mid);
rc[x]=merge(rc[x],rc[y],mid+1,r);
return x;
}
void dfs(int x){
for(int i=0;i<v[a[x]].size();i++) change(rt[x],1,up,v[a[x]][i]);
for(auto to:g[x]){dfs(to); flag=x; rt[x]=merge(rt[x],rt[to],1,up);}
}
signed main(){
get(1e5); cin>>n;
for(int i=2,x;i<=n;i++) scanf("%d",&x),g[x].push_back(i);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),up=max(up,a[i]);
memset(res,-1,sizeof res); dfs(1);
for(int i=1;i<=n;i++) printf("%d
",res[i]);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
hdu4671(다교리그 7--수 시뮬레이션)클릭하여 링크 열기 제목: n과 서버, m개의 데이터베이스가 있고 모든 데이터베이스는 서버를 연결해야 하지만 모든 데이터베이스는 서버를 연결하는 우선순위가 있습니다.모든 데이터베이스의 서버 우선순위를 구하다.또한 한...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.