CodeForces 593D Happy Tree Party [LCA+并查集] _codeforces

冲天香阵透长安，满城尽带黄金甲。这篇文章主要讲述CodeForces 593D Happy Tree Party [LCA+并查集]相关的知识，希望能为你提供帮助。
题意：给一棵树，每条边有一个权值，给两种操作，第一种是询问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){ 17if(k==pre[k]) return k; 18return pre[k]=find(pre[k]); //并查集 19 } 20 void dfs(int u,int fa){ 21g[u]=fa; //u的爸爸 22for(pii x:f[u]){ 23if(x.fi==fa) continue; 24pos[x.fi]=x.se; //记录每个点对应的边权的编号，边权转点权 25dep[x.fi]=dep[u]+1; //计算深度 26dfs(x.fi,u); 27} 28 } 29 void up(int u){ 30pre[u]=g[u]; //u变成u的爸爸 31 } 32 ll lca(int a,int b,ll y){ 33a=find(a),b=find(b); 34while(a!=b){ 35if(dep[a]< dep[b]) swap(a,b); //每次将较深的点向上找 36if(val[pos[a]]==1) up(a); //点权为1时，压缩该点 37y/=val[pos[a]]; a=find(g[a]); //除以该点的权值 38if(y==0) return 0; //y为0直接跳出 39} 40return y; 41 } 42 int main(){ 43ios::sync_with_stdio(false); 44//freopen("in","r",stdin); 45cin> > n> > m; 46for(int i=0; i< =n; i++) pre[i]=i; 47for(int i=1,u,v; i< n; i++){ 48cin> > u> > v> > val[i]; 49f[u].push_back(pii(v,i)); 50f[v].push_back(pii(u,i)); 51} 52dfs(1,0); 53for(int i=1; i< =m; i++){ 54int op,a,b,p; 55ll c,y; 56cin> > op; 57if(op==1){ 58cin> > a> > b> > y; 59cout< < lca(a,b,y)< < endl; 60}else{ 61cin> > p> > c; 62val[p]=c; 63} 64} 65return 0; 66 }

【CodeForces 593D Happy Tree Party [LCA+并查集]】