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;i<=H;i++)    if (!pf[i])    {      for (int j=i;j<=H;j+=i)        fac[j].push(i),pf[j]=1;    }}void dfs(int k,int fa){  int P=data[k];  for (int i=0;i<fac[P].size();i++)  {    int go=fac[P][i],temp=f[go].size();    if (temp&&deep[f[go][temp-1]]>deep[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[P].size();i++)    f[fac[P][i]].pop();}inline void get_deep(int k,int fa){  for (int i=end[k];i;i=a[i].next)    if (a[i].go!=fa) deep[a[i].go]=deep[k]+1,get_deep(a[i].go,k);}int main(){  scanf("%d%d",&n,&Q);  for (i=1;i<=n;i++)    scanf("%d",&data[i]);  for (i=1;i<n;i++)    scanf("%d%d",&x,&y),add(x,y),add(y,x);  init();deep[0]=-1;get_deep(1,0);  memset(ans,0,sizeof(ans));dfs(1,0);  while (Q--)  {    scanf("%d%d",&opt,&x);    if (opt==1) {printf("%d\n",ans[x]?ans[x]:-1);continue;}    memset(ans,0,sizeof(ans));    scanf("%d",&y);data[x]=y;dfs(1,0);  }  return 0;}