Tamref love random numbers, but he hates recurrent relations, Tamref thinks that mainstream random generators like the linear congruent generator suck. That's why he decided to invent his own random generator.
As any reasonable competitive programmer, he loves trees. His generator starts with a tree with numbers on each node. To compute a new random number, he picks a rooted subtree and multiply the values of each node on the subtree. He also needs to compute the number of divisors of the generated number (because of cryptographical applications).
In order to modify the tree (and hence create different numbers on the future), Tamref decided to perform another query: pick a node, and multiply its value by a given number.
Given a initial tree T, where T__u corresponds to the value on the node u, the operations can be summarized as follows:
- RAND: Given a node u compute
and count its divisors, where T(u) is the set of nodes that belong to the subtree rooted at u.
- SEED: Given a node u and a number x, multiply T__u by x.
Tamref is quite busy trying to prove that his method indeed gives integers uniformly distributed, in the meantime, he wants to test his method with a set of queries, and check which numbers are generated. He wants you to write a program that given the tree, and some queries, prints the generated numbers and count its divisors.
Tamref has told you that the largest prime factor of both T__u and x is at most the Tamref's favourite prime: 13. He also told you that the root of T is always node 0.
The figure shows the sample test case. The numbers inside the squares are the values on each node of the tree. The subtree rooted at node 1 is colored. The RAND query for the subtree rooted at node 1 would generate 14400, which has 63 divisors.
Input
The first line is an integer n (1 ≤ n ≤ 105), the number of nodes in the tree T. Then there are n - 1 lines, each line contains two integers u and v (0 ≤ u, v < n) separated by a single space, it represents that u is a parent of v in T. The next line contains n integers, where the i - th integer corresponds to T__i (1 ≤ T__i ≤ 109). The next line contains a number Q (1 ≤ Q ≤ 105), the number of queries. The final Q lines contain a query per line, in the form "RAND u" or "SEED u x" (0 ≤ u < n, 1 ≤ x ≤ 109).
Output
For each RAND query, print one line with the generated number and its number of divisors separated by a space. As this number can be very long, the generated number and its divisors must be printed modulo 109 + 7.
Example
Input
80 10 21 32 42 53 63 77 3 10 8 12 14 40 153RAND 1SEED 1 13RAND 1
Output
14400 63187200 126题意：给一颗树共n个点，以及其结点的数值ai，有q次行为，查询询问子树(包括节点)的数值的积，与更新单个节点即乘题给数(一开始以为是整个子树都要更新)思路：明显的线段树题，但是问题是线段树里存的是什么。如果直接存积，数组开long long也存不下。那么就需要换种思路，存积的质因子的指数。即把积X=(p1^a)*(p2^b)*(p3^c)*······中的a,b,c用数组记录。又题目给出子树结点的积可以用不超过13的素数的积来表示。则定义一个b[]={2,3,5,7,11,13}。就能表示所有子树积。这样查询到以后可以直接用快速幂求得第一问，用乘法原理因子数=(a+1)*(b+1)······即得第二问。想到这里剩下的操作就是套+改线段树dfs序板子了(这里膜一下月老tql)
1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 #include<iostream>
5 #include<vector>
6 #include<queue>
7 #include<cmath>
8 #include<set>
9 #define lid id<<1
10 #define rid id<<1|1
11 #define INF 0x3f3f3f3f
12 #define LL long long
13 #define debug(x) cout << "[" << x << "]" << endl
14 using namespace std;
15 const int maxn = 1e5+5;
16 int b[]={2,3,5,7,11,13};
17 int d[maxn][6]={0};
18 void cal(int x, int *d)
19 {
20 for(int i = 0;i < 6 ;i++){
21 while(x%b[i]==0)x/=b[i],d[i]++;
22 }
23 }
24 const int mx = 1e5+10;
25 const int mod = 1e9+7;
26 int L[mx], R[mx], p[mx];
27 struct tree{
28 int l, r;
29 int p[6]; //2,3,5,7,11,13
30 int lazy[6];
31 }tree[mx<<2];
32 vector<int> G[mx];
33 int cnt;
34 LL Ans[6] = {0};
35
36 LL qpow(LL x, LL n){ //x^n
37 LL res = 1;
38 while (n > 0){
39 if (n & 1) res = res*x%mod;
40 x = x*x % mod;
41 n >>= 1;
42 }
43 return res;
44 }
45
46 void push_up(int id){
47 for (int i = 0; i < 6; i++)
48 tree[id].p[i] = tree[lid].p[i]+tree[rid].p[i];
49 }
50
51 void build(int l, int r, int id){
52 tree[id].l = l;
53 tree[id].r = r;
54 for (int i = 0; i < 6; i++) tree[id].p[i] = 0;
55 if (l == r) return;
56 int mid = (l+r) >> 1;
57 build(l, mid, lid);
58 build(mid+1, r, rid);
59 }
60
61 void dfs(int u){
62 L[u] = ++cnt;
63 int len = G[u].size();
64 for (int i = 0; i < len; i++){
65 int v = G[u][i];
66 dfs(v);
67 }
68 R[u] = cnt;
69 }
70
71 void upd(int c, int id, int *x){
72 if (tree[id].l == c && tree[id].r == c){
73 for (int i = 0; i < 6; i++)
74 tree[id].p[i] += x[i];
75 return;
76 }
77 int mid = (tree[id].l + tree[id].r)>>1;
78 if (c <= mid) upd(c, lid, x);
79 else upd(c, rid, x);
80 push_up(id);
81 }
82
83 void query(int l, int r, int id){
84 if (tree[id].l == l && tree[id].r == r){
85 for (int i = 0; i < 6; i++)
86 Ans[i] += tree[id].p[i];
87 return;
88 }
89 int mid = (tree[id].l + tree[id].r)>>1;
90 if (r <= mid) query(l, r, lid);
91 else if (mid < l) query(l, r, rid);
92 else {
93 query(l, mid, lid);
94 query(mid+1, r, rid);
95 }
96 }
97
98 int main(){
99 int n, u, v, a, q;
100 cnt = 0;
101 scanf("%d", &n);
102 for (int i = 1; i < n; i++){
103 scanf("%d%d", &u, &v);
104 G[u].push_back(v);
105 p[v] = u;
106 }
107 for (int i = 0; i < n; i++){
108 if (!p[i]) {
109 dfs(i);
110 break;
111 }
112 }
113 build(1, n, 1);
114 for (int i = 0; i < n; i++){
115 scanf("%d", &a);
116 cal(a,d[i]);
117 upd(L[i], 1, d[i]);
118 }
119 scanf("%d", &q);
120 while (q--){
121 char s[10];
122 int d2[6] = {0};
123 scanf("%s%d", s, &a);
124 if (s[0] =='R'){
125 memset(Ans, 0, sizeof Ans);
126 query(L[a], R[a], 1);
127 LL ans = 1;
128 LL num = 1;
129 for (int i = 0; i < 6; i++){
130 num = (num*qpow(b[i], Ans[i]))%mod;
131 ans = ans*(Ans[i]+1)%mod;
132 }
133 printf("%lld %lld\n", num, ans);
134 }
135 else {
136 int c;
137 scanf("%d", &c);
138 cal(c, d2);
139 upd(L[a], 1, d2);
140 }
141 }
142 return 0;
143 }
View Code
