题解 CF593D 【Happy Tree Party】

· · 题解

看到这个题目，由于不是很会树链剖分、LCT等高级算法，于是考虑用LCA做这个题目

思路很简单，对于每一次查询，直接找到两点的LCA，由于边权很大而且要动态改边，所以两个点要一步一步跳到LCA，在这个过程中将V除以经过的边权，改边的话直接对链式前向星进行修改

然后就妥妥的TLE了。。。

此时仔细观察题面，可以发现一些有趣的性质：

虽然边权范围给的很大，但是初始值也只有10^{18}这么大，也就是一次查询最多经过边权大于1的边log_2 10^{18} \approx 60 次

这样的话，就可以想到用并查集优化这个做法：把边权为1的边的目标节点记入它父亲节点的并查集，然后查询时两个点往LCA跳的过程中稍作修改，并且当V变成0时直接跳出，那么每次至多跳60次，而且往往会比60小很多，这样就可以用LCA的做法AC本题

具体细节见代码

#include<iostream>
#include<cstdio>
#include<cctype>
#define E puts("E?")
#define ll long long
using namespace std;
inline ll read(){
    ll w=0,s=1;
    char c=getchar();
    while(!isdigit(c)){
        s=(c=='-')?-1:1;
        c=getchar();
        }
    while(isdigit(c)){
        w=(w<<3)+(w<<1)+c-'0';
        c=getchar();
        }
    return w*s; 
    }
const int N=200005;
ll pre[N],cnt;
struct Edge{
    ll nxt,to,wei,from;//链式前向星多记录一个from方便改边权
    };
Edge edge[N<<1];
void add_for(ll u,ll v,ll w){
    edge[++cnt].nxt=pre[u];
    edge[cnt].to=v;
    edge[cnt].wei=w;
    edge[cnt].from=u;
    pre[u]=cnt;
    }
ll f[N][21],dep[N],fa[N],va[N];
ll find(ll x){
    return fa[x]==x?x:fa[x]=find(fa[x]);//并查集
    }
void search(ll u,ll grt){
    f[u][0]=grt;
    dep[u]=dep[grt]+1;
    for(ll i=1;i<=17;i++){
        f[u][i]=f[f[u][i-1]][i-1];
        }
    for(ll i=pre[u];i>0;i=edge[i].nxt){
        ll v=edge[i].to,w=edge[i].wei;
        if(v!=grt){
            if(w==1){
                fa[v]=find(u);//在做LCA初始化的时候，遇到边权为1的边就可以把目标节点合并到父亲节点了
                }
            va[v]=w;//并查集的权值    
            search(v,u);
            }
        }
    }
ll LCA(ll u,ll v){
    if(dep[u]<dep[v]){
        swap(u,v);
        }
    for(ll i=17;i>=0;i--){
        if(dep[f[u][i]]>=dep[v]){
            u=f[u][i];
            }
        if(u==v){
            return u;
            }   
        }
    for(ll i=17;i>=0;i--){
        if(f[u][i]!=f[v][i]){
            u=f[u][i];
            v=f[v][i];
            }
        }
    return f[u][0]; 
    }   
ll n,q; 
int main(){
    n=read();
    q=read();
    ll u,v,w;
    for(ll i=1;i<n;i++){
        u=read();
        v=read();
        w=read();
        add_for(u,v,w);
        add_for(v,u,w);//无向图连两条边
        }
    for(ll i=1;i<=n;i++){
        fa[i]=i;//并查集初始化
        }   
    search(1,0);    
    ll opt,x,y,z;
    for(ll p=1;p<=q;p++){
        opt=read();
        if(opt==1){//查询操作
            x=read();
            y=read();
            z=read();
            ll anc=LCA(x,y),a=x,b=y;
            while(dep[a]>dep[anc]&&z){//"&&z"就是当v为0时可以不用再跳了
                if(va[a]){  
                    z/=va[a];
                    }
                a=find(f[a][0]);//借助并查集，每次上跳不是简单的跳到父亲，而是父亲所在并查集的祖先（？）   
                }
            while(dep[b]>dep[anc]&&z){
                if(va[b]){
                    z/=va[b];
                    }
                b=find(f[b][0]);    
                }   
            printf("%lld\n",z);     
            }
        else{//修改操作
            x=read();
            y=read();
            ll u=edge[x<<1].from,v=edge[x<<1].to;
            if(f[u][0]==v){
                z=u;//由于我们做并查集的时候是把儿子并入父亲，所以改边时要看from和to哪个在树上是父亲
                }
            else{
                z=v;
                }   
            va[z]=y;
            if(va[z]==1){
                fa[z]=find(f[z][0]);//边权为1就合并
                }
            }   
        }
    return 0;
    }

GL~