D题，LCA是很明显的。要注意的是，因为是除法，所以最多可以除x>2的有64次，当大于64时可以直接返回0。而且注意到可能会有很多值为1的边，可以使用路径压缩，把边为1的边压缩掉，类似于并查集的路径压缩。

之前只压缩到LCA，一直TLE，可以直接压缩到它们的根节点。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define LL long longusing namespace std;const int MAX=200050;int head[MAX],tot;struct Edge{ int u,v,next; LL w;}edge[MAX*2];LL w[MAX]; int pre[MAX],depth[MAX],edno[MAX],par[MAX][20];bool vis[MAX];queue
           
            que;void addedge(int u,int v,LL w){ edge[tot].u=u; edge[tot].v=v; edge[tot].w=w; edge[tot].next=head[u]; head[u]=tot++;}int n,m;void BFS(int u){ que.push(u); depth[u]=1; edno[u]=0; while(!que.empty()){ u=que.front(); vis[u]=true; que.pop(); for(int e=head[u];e!=-1;e=edge[e].next){ int v=edge[e].v; if(vis[v]) continue; depth[v]=depth[u]+1; par[v][0]=u; if(w[edno[u]]==1){ pre[v]=pre[u]; edno[v]=edge[e].w; } else{ pre[v]=u; edno[v]=edge[e].w; } que.push(v); } }}void init(){ int i,j; for(j=1;(1<
            
             <=n;j++) for(i=1;i<=n;i++) if(par[i][j-1]!=-1) par[i][j]=par[par[i][j-1]][j-1];}int LCA(int a,int b)//最近公共祖先{ int i,j; if(depth[a]
             
              =0;j--) if(depth[a]-(1<
              
               =depth[b]) a=par[a][j]; if(a==b)return a; //倍增法，每次向上进深度2^j，找到最近公共祖先的子结点 for(j=i;j>=0;j--){ if(par[a][j]!=-1&&par[a][j]!=par[b][j]){ a=par[a][j]; b=par[b][j]; } } return par[a][0];}LL anum[70];LL bnum[70];LL query(int a,int b,LL y){ int ret=(int)(log((double)y)/log(2.0)); int lca=LCA(a,b);/// cout<
               
                <<" "<
                
                 <
                 
                  depth[lca]){ cout<
                  <<" "<
                   
                    <
                    
                     1){ y/=w[edno[a]]; if(y==0) return 0; } int tp=pre[a]; while(pre[tp]!=-1&&w[edno[tp]]==1){ tp=pre[tp]; } int rt=tp; tp=a; while(pre[tp]!=rt){ int tmp=pre[tp]; pre[tp]=rt; tp=tmp; } a=rt; } LL ty=y; while(b!=-1&&depth[b]>depth[lca]){/// cout<
                     <<" "<
                      
                       <
                       
                        1){ ty/=w[edno[b]]; bnum[bc++]=w[edno[b]]; if(ty==0) return 0; } int tp=pre[b]; while(pre[tp]!=-1&&w[edno[tp]]==1){ tp=pre[tp]; } int rt=tp; tp=b; while(pre[tp]!=rt){ int tmp=pre[tp]; pre[tp]=rt; tp=tmp; } b=rt; }/// cout<
                        
                         <<" "<
                         
                          <
                          
                           =0;i--) y/=bnum[i]; return y;}int main(){ int u,v,op,a,b,p,c; LL y; while(scanf("%d%d",&n,&m)!=EOF){ memset(pre,-1,sizeof(pre)); memset(head,-1,sizeof(head)); memset(depth,0,sizeof(depth)); memset(vis,false,sizeof(vis)); memset(w,0,sizeof(w)); memset(par,-1,sizeof(par)); memset(edno,0,sizeof(edno)); tot=0; for(int i=1;i
                           
                            >u>>v>>w[i]; addedge(u,v,i); addedge(v,u,i); } BFS(1); /// cout<
                            
                             <<" "<
                             
                              <
                              
                               >a>>b>>y; cout<
                               
                                <
                                
                                 >p>>y; w[p]=y; } } } return 0;}