Um_nik

Untitled

Jul 29th, 2021
887
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N=110005;
  5. int n,Q,dfn[N],ed[N];
  6. vector<pair<int,int> > e[N];
  7. int fa[N][20],dep[N];
  8. long long dis[N];
  9. void dfs(int x){
  10.     dfn[x]=++*dfn;
  11.     for (auto i:e[x])
  12.         if (i.first!=fa[x][0]){
  13.             fa[i.first][0]=x;
  14.             dep[i.first]=dep[x]+1;
  15.             dis[i.first]=dis[x]+i.second;
  16.             dfs(i.first);
  17.         }
  18.     ed[x]=*dfn;
  19. }
  20.  
  21. vector<int> di[N];
  22. void init(){
  23.     for (int i=1;i<N;i++)
  24.         for (int j=i;j<N;j+=i)
  25.             di[j].push_back(i);
  26. }
  27.  
  28. struct node{
  29.     int x,l,r,id;
  30. };
  31. vector<node> op[N];
  32. long long ans[N];
  33.  
  34. const int M=20000005;
  35. int ls[M],rs[M],S[M],nd;
  36. int rt[N];
  37. void change(int &k,int l,int r,int x,int v){
  38.     if (!k) k=++nd; S[k]+=v;
  39.     if (l==r) return;
  40.     int mid=(l+r)/2;
  41.     if (x<=mid) change(ls[k],l,mid,x,v);
  42.     else change(rs[k],mid+1,r,x,v);
  43. }
  44. int ask(int k,int l,int r,int x,int y){
  45.     if ((x<=l&&r<=y)||!k) return S[k];
  46.     int mid=(l+r)/2;
  47.     if (y<=mid) return ask(ls[k],l,mid,x,y);
  48.     if (x>mid) return ask(rs[k],mid+1,r,x,y);
  49.     return ask(ls[k],l,mid,x,mid)+ask(rs[k],mid+1,r,mid+1,y);
  50. }
  51. void erase(int x,int y){
  52.     for (;x<=n;x+=x&(-x)) rt[x]=0;
  53. }
  54. void change(int x,int y,int v){
  55.     //cout<<"C"<<x<<' '<<y<<' '<<v<<endl;
  56.     for (;x<=n;x+=x&(-x)) change(rt[x],1,n,y,v);
  57. }
  58. int query(int x,int l,int r){
  59.     //cout<<"Q"<<x<<' '<<l<<' '<<r<<endl;
  60.     int s=0;
  61.     for (;x;x-=x&(-x)) s+=ask(rt[x],1,n,l,r);
  62.     return s;
  63. }
  64. void solve(int x){
  65.     for (auto i:op[x])
  66.         if (!i.id){
  67.             change(dfn[i.x],i.l,1);
  68.             change(ed[i.x]+1,i.l,-1);
  69.         }
  70.         else{
  71.             int p=i.x;
  72.             int val=query(dfn[p],i.l,i.r);
  73.             //cout<<val<<endl;
  74.             if (!val){
  75.                 ans[i.id]=-1;
  76.                 continue;
  77.             }
  78.             for (int j=16;j>=0;j--)
  79.                 if (fa[p][j])
  80.                     if (query(dfn[fa[p][j]],i.l,i.r)==val)
  81.                         p=fa[p][j];
  82.             ans[i.id]=dis[i.x]-dis[p];
  83.             //cout<<i.x<<' '<<p<<' '<<dis[i.x]<<' '<<dis[p]<<endl;
  84.         }
  85.    
  86.     for (;nd;--nd) ls[nd]=rs[nd]=S[nd]=0;
  87.     for (auto i:op[x])
  88.         if (!i.id){
  89.             erase(dfn[i.x],i.l);
  90.             erase(ed[i.x]+1,i.l);
  91.         }
  92. }
  93. int main(){
  94.     init();
  95.     scanf("%d%d",&n,&Q);
  96.     for (int i=1;i<n;i++){
  97.         int x,y,v;
  98.         scanf("%d%d%d",&x,&y,&v);
  99.         e[x].push_back(pair<int,int>(y,v));
  100.         e[y].push_back(pair<int,int>(x,v));
  101.     }
  102.     dfs(1);
  103.    
  104.     for (int i=1;i<=18;i++)
  105.         for (int j=1;j<=n;j++)
  106.             fa[j][i]=fa[fa[j][i-1]][i-1];
  107.    
  108.     for (int i=1;i<=Q;i++){
  109.         int tp,a,b,c,d;
  110.         scanf("%d%d%d",&tp,&a,&b);
  111.         if (tp==0){
  112.             for (auto j:di[b])
  113.                 op[j].push_back((node){a,b,0,0});
  114.             ans[i]=(-(1ll<<62));
  115.         }
  116.         else{
  117.             scanf("%d%d",&c,&d);
  118.             op[d].push_back((node){a,b,c,i});
  119.         }
  120.     }
  121.    
  122.     for (int i=1;i<=n;i++)
  123.         solve(i);
  124.  
  125.     for (int i=1;i<=Q;i++)
  126.         if (ans[i]!=-(1ll<<62))
  127.             if (ans[i]<0) puts("Impossible!");
  128.             else printf("%lld\n",ans[i]);
  129. }
RAW Paste Data