hdu 6430 TeaTree 线段树合并_Dale_zero的博客-程序员秘密

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6430

对每个节点开一颗线段树，标程的写法很节省空间：预处理出每个数字的因数，对题目中给定的权值建线段树，如果子树区间中没有根节点权值的因数，那么直接剪掉。然后通过改变每个根节点左右孩子数组的值，来改变其指向的子树根节点（即合并过程）。相当于是一棵精简的线段树。

因为权值最大为1e5，所以nlognlogn不会T。

合并时对每一对父子节点都尽可能地找到底（s==t）如果能到达底部，说明父子节点都有这个因数，s（或者t）就可能是gcd的最大值，将其与ans值比较更新。而因为每一个节点在以其为根的子树中总是最后被遍历的，所以在此过程中就符合了LCA的要求。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define mod 1000000007
#define For(i,m,n) for(int i=m;i<=n;i++)
#define Dor(i,m,n) for(int i=m;i>=n;i--)
#define LL long long
#define lan(a,b) memset(a,b,sizeof(a))
#define sqr(a) a*a
using namespace std;


const int maxn=100005;
int tot;

vector<int> d[maxn];
int ls[maxn*400],rs[maxn*400];
int ans[maxn],f[maxn],root[maxn];
int fa;
void init()
{
    For(i,1,maxn-5)
        for(int j=1;j*i<=maxn-5;j++)
            d[j*i].push_back(i);
}

void build(int& x,int s,int t,int pos)
{
    if(!x){x=++tot;ls[x]=rs[x]=0;}
    if(s==t)return;
    int mid=(s+t)>>1;
    if(pos>mid)build(rs[x],mid+1,t,pos);
    else build(ls[x],s,mid,pos);
}

int merge(int x,int y,int s,int t)
{
    if(!x||!y) return x^y;
    if(s==t){ans[fa]=max(ans[fa],s);return x;}
    int mid=(s+t)>>1;
    ls[x]=merge(ls[x],ls[y],s,mid);
    rs[x]=merge(rs[x],rs[y],mid+1,t);
    return x;
}

int main()
{
    int n;
    init();
    while(~scanf("%d",&n))
    {
        lan(ans,-1);
        For(i,2,n)
            scanf("%d",&f[i]);
            int x;
        tot=0;
        For(i,1,n)
        {
            scanf("%d",&x);
            root[i]=++tot;
            ls[tot]=rs[tot]=0;
            For(j,0,d[x].size()-1)
                build(root[i],1,1e5,d[x][j]);
        }
        Dor(i,n,1)
        {
            fa=f[i];
            root[fa]=merge(root[fa],root[i],1,1e5);
        }
        For(i,1,n)
            printf("%d\n",ans[i]);
    }
    return 0;
}

本文链接：https://blog.csdn.net/Dale_zero/article/details/82027470

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

UE4 Datasmith 导入流程源码分析_wblong_cs的博客-程序员秘密_ue4源码分析

UE4 Datasmith 导入流程源码分析导入入口函数：Engine\Plugins\Enterprise\DatasmithImporter\DatasmithImporter\Private\DatasmithImporterModule.cppvoid FDatasmithImporterModule::SetupMenuEntry(){ if (!IsRunningCommandlet()) { FDatasmithUIManager::Get().AddM

SpringBoot博客系统之后台登陆和拦截器配置_今天你学习了么的博客-程序员秘密

登陆的实现逻辑很简单，只需要根据传入的用户名和密码做出相应的判断并和数据库中数据匹配即可基本实现1. controller层，先对传入的用户名和密码进行非空判断再调用Service层进行数据库匹配，如果匹配成功则把用户信息存到session域中，并且重定向到admin/index请求，返回index页主要，因为这里涉及到了表单的提交所以再跳转页的时候一定要使用重定向请求转发和直接返回inde...

IT互联网的一些职位的简称_szh199317的博客-程序员秘密_互联网产品经理简称

互联网各职位的简称 :PM&nbsp;(&nbsp;Product Manager&nbsp;)&nbsp;产品经理：&nbsp; &nbsp;&nbsp; &nbsp; 产品的构想、框架的设计、用户的调研等。UE（User&nbsp;Experience，简称UX或&nbsp;UE）用户体验：&nbsp; &nbsp;&nbsp; &nbsp; 还有个组合叫法：UED（产品交互设计师，用

04 | 语法分析_LALAAYANG的博客-程序员秘密_语法分析是什么

04 | 语法分析语法分析程序（语法分析器）概述自上而下分析法前述递归下降分析法预测分析法（ LL(1)分析法）自下而上分析法前述算符优先分析法LR分析法LR(0)语法分析程序（语法分析器）概述输入：词法分析器生成的单词符号序列输出：语法树详述：语法分析器的功能是以词法分析器生成的单词符号序列作为输入，根据语言的语法规则（描述程序语言语法结构的上下文无关文法），识别出各种语法成分（如表达式、语句、程序段以及整个程序等），并在分析过程中进行语法检查，检查所给单词符号序列是否是该语言的文法的一个句子

工作七八载，初次写博客。开源受益多，而今且交互。前路长又漫，且行且珍惜。_Linux运维小兵的博客-程序员秘密

杂写感想感想本人网络系统专业学渣一个，毕业已经7、8年了。刚毕业时年轻好玩，社会上随波逐流，天南地北只求快乐、义气。跟着朋友吃吃喝喝，饭馆、电网销之类都做过。慢慢发现人和人是不一样的，有的人直接就生在终点，有些人自带气运，有些人天赋出众；自己呐？既非豪富之家、又无天降横财，只是个普普通通的农村娃，吃穿住行自有一套，但是想要提高，还是要靠自己的努力。后来做运维，桌面运维、软件运维、Linux运维，一步步走到现在。计算机行业的专业性还是蛮大的，工作以后发现学的东西早就忘得一干二净，这几年来网上各种博客论

【渝粤题库】陕西师范大学200971教育经济学作业（专升本、高起本）_yuyueshool的博客-程序员秘密

《教育经济学》作业一、单选题1.我国多数学者认为,应该把教育经济学隶属于经济科学体系,属于（）。A.宏观经济学 B.微观经济学 C.部门经济学 D.产业经济学2.教育经济学是现代经济和现代教育的产物,它在西方萌芽于20世纪20年代,形成于（）年代。A.40 B.60 D.703.人力资本这一概念是由美国的( )于1935年首先使用的A.舒尔茨 B.丹尼森 C.贝克