链接：

 

题意：一棵树，有边权，

两种操作：其一，改变边权（边权只能越改越小并且大于1）。其二，给一个X（1----1e18），和a,b两点，问X / (简单路径的边权乘积)

 

思路：1.裸树链剖分，维护区间乘积就可以。。爆LL的区间直接记做一个inf。。但是不太会树链剖分，考虑一个退而求其次的方法。

 

    2.直接跑找LCA，用到边权越来越小，所以对于边权为1的点用并查集路径压缩一下，这样就可以确保log次使得X为0或者求出来值了。

PS。。开始还傻傻的用ST求了LCA。。其实根据上面的性质暴力求LCA就可以了。

 

代码：（预处理LCA的。。虽说是多此一举。。）

 

#include 
    
     using namespace std;const int MAXN = 200010;int rmq[2*MAXN],tot,head[MAXN],F[MAXN*2],P[MAXN],cnt,fat[MAXN],pa[MAXN],E[MAXN][2];long long v[MAXN];int findset(int a) {	if(pa[a] != a)  return pa[a] = findset(pa[a]);	return pa[a];}void un(int a, int b){	int a1 = findset(a),b1 = findset(b);	if(a1 != b1) pa[a1] = b1;}struct ST{    int mm[2*MAXN],dp[2*MAXN][20];    void init(int n){        mm[0] = -1;        for(int i = 1; i <= n; i++){            mm[i] = ((i&(i-1)) == 0)?mm[i-1]+1:mm[i-1];            dp[i][0] = i;        }        for(int j = 1; j <= mm[n]; j++)            for(int i = 1; i + (1<
     
      < rmq[dp[i+(1<<(j-1))][j-1]]?dp[i][j-1]:dp[i+(1<<(j-1))][j-1];    }    int query(int a,int b){        if(a > b)swap(a,b);        int k = mm[b-a+1];        return rmq[dp[a][k]] <= rmq[dp[b-(1<
      
       <
      
     
    

 

精简：

 

#include 
    
     using namespace std;const int MAXN = 200010;int tot,head[MAXN],P[MAXN],fat[MAXN],pa[MAXN],E[MAXN][2];long long v[MAXN];int findset(int a) {	if(pa[a] != a)  return pa[a] = findset(pa[a]);	return pa[a];}void un(int a, int b){	int a1 = findset(a),b1 = findset(b);	if(a1 != b1) pa[a1] = b1;}struct Edge{    int to,next;    long long val;}edge[MAXN*2];void init(){    tot = 0;    memset(head,-1,sizeof(head));    for(int i = 0; i < MAXN; i++)  pa[i] = i;    memset(fat,-1,sizeof(fat));    memset(v,-1,sizeof(v));}void addedge(int u,int v,long long c){    edge[tot].to = v;    edge[tot].val = c;    edge[tot].next = head[u];    head[u] = tot++;}void dfs(int u,int pre,int dep,long long val){    P[u] = dep;    fat[u]=pre;    v[u]=val;    if(u!=pre&&val==1) un(u,pre);    for(int i = head[u]; i != -1; i = edge[i].next){        int v = edge[i].to;        if(v == pre)continue;        dfs(v,u,dep+1,edge[i].val);    }}int main(){    int n,m,a,b,ttt=0,tp;    long long c;    scanf("%d%d",&n,&m);    init();    for(int i=0;i