<span>CodeForces 593D Happy Tree Party [LCA+并查集]</span>
题意：给一棵树，每条边有一个权值，给两种操作，第一种是询问y向下整除从a到b的最短路径中每条边的权值后y的值，第二种是改变某条边的权值。
思路：y的最大值为1e18，最多除大于等于2的数不超过60次即可将y变为0，先dfs以任意一点为根建树，记录每个点的深度和它的父结点并将边权转化为点权，
再搞个并查集，将权值为1的点压缩，即使pre[u]=g[u];(u变成u的爸爸)。
1 #include<bits/stdc++.h> 2 #define fi first 3 #define se second 4 using namespace std; 5 typedef long long ll; 6 const int inf=1e9; 7 const double PI=acos(-1); 8 const double eps=1e-6; 9 const int mod=1e9+7; 10 const int maxn=2e5+10; 11 int n,m; 12 typedef pair<int,int> pii; 13 vector<pii>f[maxn]; 14 ll val[maxn]; 15 int pos[maxn],pre[maxn],dep[maxn],g[maxn]; 16 int find(int k){ 17 if(k==pre[k]) return k; 18 return pre[k]=find(pre[k]);//并查集 19 } 20 void dfs(int u,int fa){ 21 g[u]=fa;//u的爸爸 22 for(pii x:f[u]){ 23 if(x.fi==fa) continue; 24 pos[x.fi]=x.se;//记录每个点对应的边权的编号，边权转点权 25 dep[x.fi]=dep[u]+1;//计算深度 26 dfs(x.fi,u); 27 } 28 } 29 void up(int u){ 30 pre[u]=g[u];//u变成u的爸爸 31 } 32 ll lca(int a,int b,ll y){ 33 a=find(a),b=find(b); 34 while(a!=b){ 35 if(dep[a]<dep[b]) swap(a,b);//每次将较深的点向上找 36 if(val[pos[a]]==1) up(a);//点权为1时，压缩该点 37 y/=val[pos[a]];a=find(g[a]);//除以该点的权值 38 if(y==0) return 0;//y为0直接跳出 39 } 40 return y; 41 } 42 int main(){ 43 ios::sync_with_stdio(false); 44 //freopen("in","r",stdin); 45 cin>>n>>m; 46 for(int i=0;i<=n;i++) pre[i]=i; 47 for(int i=1,u,v;i<n;i++){ 48 cin>>u>>v>>val[i]; 49 f[u].push_back(pii(v,i)); 50 f[v].push_back(pii(u,i)); 51 } 52 dfs(1,0); 53 for(int i=1;i<=m;i++){ 54 int op,a,b,p; 55 ll c,y; 56 cin>>op; 57 if(op==1){ 58 cin>>a>>b>>y; 59 cout<<lca(a,b,y)<<endl; 60 }else{ 61 cin>>p>>c; 62 val[p]=c; 63 } 64 } 65 return 0; 66 }
