【JZOJ4846】【NOIP2016提高A组集训第5场11.2】行走

题目描述

数据范围

对于70%的数据保证 n <= 1000
对于100%的数据保证 n,q <= 10^5,c_i,v_i <= 10^{18}
保证每次修改后的边权小于等于原来的边权且不会小于1

解法

由于c最大只有264，所以整除大于1的权值最多除64次，所以使用利用并查集将权值为1的边合并，然后每次询问只需寻找64条权值大于1的边即可。

---

树链剖分也是可以的。

代码

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define ll long long
#define ln(x,y) ((ll)(log(x)/log(y)))
using namespace std;
const char* fin="walk.in";
const char* fout="walk.out";
const ll inf=0x7fffffff;
const ll maxn=100007,maxm=maxn*2,maxk=20;
ll n,m,i,j,k,l,o,tot;
ll fi[maxn],la[maxm],ne[maxm],va[maxm],limit;
ll fa[maxn][maxk],w[maxn],dad[maxn],de[maxn];
ll a[maxn],b[maxn];
ll getdad(ll v){
    if (dad[v]==0) return v;
    dad[v]=getdad(dad[v]);
    return dad[v];
}
void add_line(ll a,ll b,ll c){
    tot++;
    ne[tot]=fi[a];
    la[tot]=b;
    va[tot]=c;
    fi[a]=tot;
}
void dfs(ll v,ll from){
    ll i,j,k;
    de[v]=de[from]+1;
    for (i=1,j=ln(de[v],2);i<=j;i++){
        k=fa[v][i-1];
        fa[v][i]=fa[k][i-1];
    }
    for (k=fi[v];k;k=ne[k])
        if (la[k]!=from){
            if (va[k]==1) dad[la[k]]=getdad(v);
            w[la[k]]=va[k];
            fa[la[k]][0]=v;
            dfs(la[k],v);
        }
}
ll lca(ll u,ll v){
    ll i,j,k;
    if (de[u]<de[v]) swap(u,v);
    for (i=ln(de[u]-de[v],2);i>=0;i--) if (de[fa[u][i]]>de[v]) u=fa[u][i];
    if (de[u]!=de[v]) u=fa[u][0];
    for (i=ln(de[u],2);i>=0;i--) if (fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
    if (u!=v) return fa[u][0];
    return u;
}
int main(){
    freopen(fin,"r",stdin);
    freopen(fout,"w",stdout);
    scanf("%lld%lld",&n,&m);
    for (i=1;i<n;i++){
        scanf("%lld%lld%lld",&j,&k,&l);
        add_line(j,k,l);
        add_line(k,j,l);
    }
    dfs(1,0);
    for (i=1;i<=m;i++){
        scanf("%lld",&j);
        if (j==1){
            scanf("%lld%lld%lld",&j,&k,&l);
            ll LCA=lca(j,k);
            limit=ln(l,2)+3;
            a[0]=b[0]=0;
            while (a[0]+b[0]<=limit && de[j]>de[LCA]){
                if (w[j]==1) j=getdad(j);
                else{
                    a[++a[0]]=w[j];
                    j=fa[j][0];
                }
            }
            while (a[0]+b[0]<=limit && de[k]>de[LCA]){
                if (w[k]==1) k=getdad(k);
                else{
                    b[++b[0]]=w[k];
                    k=fa[k][0];
                }
            }
            if (a[0]+b[0]>limit) printf("0
");
            else{
                for (j=1;j<=a[0];j++) l/=a[j];
                for (k=b[0];k;k--) l/=b[k];
                printf("%lld
",l);
            }
        }else{
            scanf("%lld%lld",&j,&k);
            l=la[j*2];
            o=la[j*2-1];
            if (l==fa[o][0]){
                if (w[o]!=1 && k==1) dad[o]=l;
                w[o]=k;
            }else{
                if (w[l]!=1 && k==1) dad[l]=o;
                w[l]=k;
            }
        }
    }
    return 0;
}

启发

a/b/c变成a/(b∗c)是可以的，所以可以使用树链剖分。

---

发掘题目性质，例如一个数连续整除以若干个大于1的数，不超过log次后，这个数会变为0。