CF問題集 PART7 #264 div 2 E_html/css_WEB-ITnose

【原题】

E. Caisa and Tree

テストごとの制限時間

10 秒

テストごとのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

Caisa は今家にいて、彼の息子は彼のために簡単な仕事をしています。

1 から n まで番号が付けられた、n 個の頂点を持つルート付きツリーが与えられます (頂点 1 がルートです)。ツリーの各頂点には値があります。 q 質問に答える必要があります。各クエリは次のいずれかです:

クエリの形式は「1 v」です。ルートから頂点 v までのパスに沿った頂点のシーケンスを書き出してみましょう: u1,?u2,?...,?uk (u1?=?1; uk?=?v)。 gcd(uiの値,?vの値)?>?1およびi?

クエリの形式は「2 v w」です。頂点 v の値を w に変更する必要があります。

すべてのクエリが与えられました。Caisa が問題を解決できるように手伝ってください。

入力

最初の行には、スペースで区切られた 2 つの整数 n、q (1?≤) が含まれています。 ?n,?q?≤?105).

2 行目には n 個の整数 a1,?a2,?...,?an (1?≤?ai?≤?2·106) が含まれており、ai は値を表しますノード i.

次の n?-?1 行のそれぞれには、2 つの整数 xi と yi (1?≤?xi,?yi?≤?n; xi?≠?yi) が含まれており、間のツリーの端を示します。頂点 xi と yi

次の各 q 行には、上記の形式のクエリが含まれています。各クエリについて、次の不等式が成り立ちます: 1?≤?v?≤?n および 1?≤?w?≤?2·106。 頂点の値を変更するクエリは 50 個以下であることに注意してください。

出力

最初のタイプのクエリごとに、クエリの結果が出力されます。

サンプル テスト

入力

4 610 8 4 31 22 33 41 11 21 31 42 1 91 4

出力

-112-11

注

gcd(x,?y) は 2 つの整数 x と y の最大公約数です。

【分析】これは道题です本来は能力 A ですが、= が大幅に拡張されており、ベクトルも使用できず、テーブルの麻痺が原因で終了しました。次に、この問題を徹底的に再構築し、次に各係数の最大値を設定することができます。 (これはより省スペースな)

剩下にある解決すべき問題は次のとおりです:私は dfs を使用しているため、怎么は特定の子树の情報を搜完後に再去掉しますか? (免影響响他の子树)HHD 表示用ベクトル点これも同様の思考回路を使用できますが、麻烦= =

【代】

#include<cstdio>#include<algorithm>#include<cstring>#include<vector>#define N 100005#define S 2000005#define push push_back#define pop pop_backusing namespace std;vector<int>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<fac f void get_deep k fa for i="end[k];i;i=a[i].next)" if deep main scanf init memset while return> <p> </p></fac></int></vector></cstring></algorithm></cstdio>