开发笔记:2018多校第十场HDU6430线段树合并

1 #include
2 using namespace std;
3 #define ll long long
4 #define ull unsigned long long
5 #define mst(a,b) memset((a),(b),sizeof(a))
6 #define mp(a,b) make_pair(a,b)
7 #define fi first
8 #define se second
9 #define pi acos(-1)
10 #define pii pair
11 #define pb push_back
12 const int INF = 0x3f3f3f3f;
13 const double eps = 1e-6;
14 const int MAXN = 1e5 + 10;
15 const int MAXM = 2e6 + 10;
16 const ll mod = 1e9 + 7;
17
18 vector<int>yz[MAXN],vec[MAXN];
19
20 void init() {
21 for(int i = 1; i ) {
22 for(int j = 1; j <= sqrt(i); j++) {
23 if(i % j == 0) {
24 yz[i].pb(j);
25 if(j != i / j) yz[i].push_back(i / j);
26 }
27 }
28 }
29 }
30
31 int root[MAXN];
32 int ls[MAXN * 400], rs[MAXN * 400], st[MAXN * 400];
33 int cnt = 0;
34
35 void pushup(int o) {
36 st[o] = max(st[ls[o]], st[rs[o]]);
37 }
38
39 void update(int k,int l,int r,int &o) {
40 if(!o) o = ++cnt;
41 if(l == r) {
42 st[o] = k;
43 return ;
44 }
45 int mid = (l + r) >> 1;
46 if(k <= mid) update(k, l, mid, ls[o]);
47 else update(k, mid + 1, r, rs[o]);
48 pushup(o);
49 }
50
51 int mergee(int fa,int u,int &ans) {
52 if(!fa || !u) return fa | u;
53 if(st[fa] == st[u]) ans = max(ans, st[fa]);
54 if(ls[fa] || ls[u]) ls[fa] = mergee(ls[fa], ls[u], ans);
55 if(rs[fa] || rs[u]) rs[fa] = mergee(rs[fa], rs[u], ans);
56 return fa;
57 }
58
59 int ans[MAXN];
60
61 void dfs(int u) {
62 for(int i = 0; i ) {
63 int v = vec[u][i];
64 dfs(v);
65 mergee(root[u], root[v], ans[u]);
66 }
67 }
68
69 int main() {
70 #ifdef local
71 freopen("data.txt", "r", stdin);
72 // freopen("data.txt", "w", stdout);
73 #endif
74 init();
75 int n;
76 scanf("%d",&n);
77 for(int i = 2; i <= n; i++) {
78 int f;
79 scanf("%d",&f);
80 vec[f].push_back(i);
81 }
82 for(int i = 1; i <= n; i++) {
83 int x;
84 scanf("%d",&x);
85 for(int j = 0; j )
86 update(yz[x][j], 1, 1e5, root[i]);
87 }
88 mst(ans, -1);
89 dfs(1);
90 for(int i = 1; i <= n; i++)
91 printf("%d
",ans[i]);
92 return 0;
93 }