题面
“我有个愿望，我希望走到你身边。”
这是个奇异的世界，世界上的n-1条路联结起来形成一棵树，每条路有一个对应的权值ci。
现在我会给出q组询问或操作。
每次询问我会从一个x点走到y点，初始在x点我会有一个数字v，然后每走过一条权值为c的边，我的v就会变成v/c(向下取整),问最后到y时v变成了什么。
每次修改我会修改一条边的权值，保证修改后的权值小于等于原来的权值且不会小于1。
每组询问或操作的格式如下：
询问：1 x y v表示从x走到y，一开始的数字为v。
操作：2 p c表示将第p条边的边权修改为c
对于70%的数据保证n<=1000
对于100%的数据保证n,q<=100000,c_i,v_i <= 10^{18}
保证每次修改后的边权小于等于原来的边权且不会小于1
分析
分析啥啊，我打的暴力啊？为啥过了？？懵逼中
代码
#include<bits/stdc++.h> using namespace std; #define N 100100 #define ll long long int n,q,op,ans,cnt,tot; ll val[N]; int dep[N],first[N],f[N][20],fc[N]; struct email {int u,v;ll w;int nxt; }e[N*4]; inline void add(int u,int v,ll w) {e[++cnt].nxt=first[u];first[u]=cnt;e[cnt].u=u;e[cnt].v=v;e[cnt].w=w; } inline void read(int &x) {x=0;int fh=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')fh=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}x*=fh; } inline void readl(ll &x) {x=0;int fh=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')fh=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}x*=fh; }void pre(int u,int fa) {for(int i=1;(1<<i)<=dep[u];i++)f[u][i]=f[f[u][i-1]][i-1];for(int i=first[u];i;i=e[i].nxt){int v=e[i].v;if(v==fa)continue;dep[v]=dep[u]+1;f[v][0]=u;pre(v,u);} }inline int lca(int x,int y) {int len=1;if(dep[x]<dep[y])swap(x,y);int t=dep[x]-dep[y];for(int i=0;(1<<i)<=t;i++)if(t&(1<<i))x=f[x][i];if(x==y)return x;for(int i=19;i>=0;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];return f[x][0]; }void dfs(int u,int fa,int tar,int k) {for(int i=first[u];i;i=e[i].nxt){int v=e[i].v;ll w=e[i].w;if(v==fa||dep[v]>dep[u])continue;val[k]/=w;if(v==tar)return;dfs(v,u,tar,k);} }void solve1() {for(int i=1;i<=q;i++){read(op);if(op==1){int x,y,pref;ll v;read(x);read(y);readl(v);val[++tot]=v;pref=lca(x,y);if(x!=pref)dfs(x,x,pref,tot);if(y!=pref)dfs(y,y,pref,tot);printf("%lld\n",val[tot]);}if(op==2){int p,c;read(p);read(c);e[fc[p]].w=c;e[fc[p]+1].w=c;}} }int main() {read(n);read(q);for(int i=1;i<n;i++){int u,v;ll w;read(u);read(v);readl(w);add(u,v,w);fc[i]=cnt;add(v,u,w);}pre(1,0);solve1();return 0;}