CF 题目集锦 PART 7 #264 div 2 E_html/css_WEB-ITnose
E. Caisa and Tree
time limit per test
10 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Caisa is now at home and his son has a simple task for him.
Given a rooted tree with n vertices, numbered from 1 to n (vertex 1 is the root). Each vertex of the tree has a value. You should answer q queries. Each query is one of the following:
You are given all the queries, help Caisa to solve the problem.
Input
The first line contains two space-separated integers n, q (1?≤?n,?q?≤?105).
The second line contains n integers a1,?a2,?...,?an (1?≤?ai?≤?2·106), where ai represent the value of node i.
Each of the next n?-?1 lines contains two integers xi and yi (1?≤?xi,?yi?≤?n; xi?≠?yi), denoting the edge of the tree between vertices xi and yi.
Each of the next q lines contains a query in the format that is given above. For each query the following inequalities hold: 1?≤?v?≤?n and 1?≤?w?≤?2·106. Note that: there are no more than 50 queries that changes the value of a vertex.
Output
For each query of the first type output the result of the query.
Sample test(s)
input
4 610 8 4 31 22 33 41 11 21 31 42 1 91 4
output
-112-11
Note
gcd(x,?y) is greatest common divisor of two integers x and y.
【分析】这道题是做现场赛的。本来能A的,但是太紧张了=而且也不会用vector,边表搞的麻烦死了。
开始看到修改操作才50次、时间又松,真是爽!估计每次可以暴力重构这颗树,然后对于每个质因子记录最优值。
首先每次不能sqrt的效率枚举一个数的因子,我们可以预处理出每个数的所有质因子。(其实有更省空间的)
剩下来要解决的问题是:因为我是用dfs的,怎么把某个子树的信息在搜完后再去掉?(以免影响其他子树)HHD表示用vector一点也不虚。其实应该也可以用边表类似的思路,但是麻烦= =
【代码】
#include#include #include #include #define N 100005#define S 2000005#define push push_back#define pop pop_backusing namespace std;vector fac[S],f[S];int data[N],ans[N],end[N],pf[S],deep[N];int C,cnt,n,Q,i,x,y,opt;struct arr{int go,next;}a[N*2];inline void add(int u,int v){a[++cnt].go=v;a[cnt].next=end[u];end[u]=cnt;}inline void init(){ int H=2000000; for (int i=2;ideep[ans[k]]) ans[k]=f[go][temp-1]; f[go].push(k); } for (int i=end[k];i;i=a[i].next) if (a[i].go!=fa) dfs(a[i].go,k); for (int i=0;i