题目描述
“我有个愿望，我希望走到你身边。”
这是个奇异的世界，世界上的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
输入
第一行两个整数n和q表示点个数和询问与操作个数
接下来n-1行每行三个整数u,v,c表示u与v之间有一条边权为c的边
接下来q行每行第一个数type
如果type=1那么接下来三个数x,y,v表示一组询问
如果type=2那么接下来两个数p,c表示一组操作
输出
对于每组询问输出一个数表示最后的答案
样例输入1
样例输出1
样例输入2
样例输出2
数据范围
对于70%的数据保证1<=n<=1000
对于100%的数据保证1<=n<=100000,1<=ci<=10^18
保证每次修改后的边权小于等于原来的边权且不会小于1
题解：
由于对于百分之百的数据，ci可能会出现10^18。
而对于题目中[v/c]的操作，有几个可以利用的性质：
1）出现一段连续的边c=1时，不需要操作
2）当边数超过62时，答案必定为0
证明2）：对∨x∈[1,+∞)，x^62>10^18
因此，对于连续的边出现c=1时，用并查集将这些边集的子集合并，方便操作；对于2）还可以判断当边数>62时，直接输出'0'
#include<stdio.h>
#include<string.h>
#define N 100001
using namespace std;
typedef long long ll;
inline int Fs(){
int x=,c=getchar(),f=;
for(;c<||c>;c=getchar())
if(!(c^))
f=-;
for(;c>&&c<;c=getchar())
x=(x<<)+(x<<)+c-;
return x*f;
}
inline ll Fl(){
ll x=,c=getchar(),f=;
for(;c<||c>;c=getchar())
if(!(c^))
f=-;
for(;c>&&c<;c=getchar())
x=(x<<)+(x<<)+c-;
return x*f;
}
struct edge{
ll w;
int v,nxt;
}e[N<<];
ll s[N],s1[N],s2[N];
int n,fst[N],fa[N],dep[N],f[N];
inline void link(int a,int b,ll c){
static int tt;
e[++tt].w=c,
e[tt].v=b,
e[tt].nxt=fst[a],
fst[a]=tt;
}
void dfs(int x){
for(int j=fst[x];j;j=e[j].nxt)
if(!fa[e[j].v])
fa[e[j].v]=x,
s[e[j].v]=e[j].w,
dep[e[j].v]=dep[x]+,
dfs(e[j].v);
}
int bin(int x){
int p1,p2=x;
for(;x^f[x];x=f[x])
;
for(;p2^f[p2];)
p1=f[p2],
f[p2]=x,
p2=p1;
return x;
}
int main(){
freopen("walk.in","r",stdin),
freopen("walk.out","w",stdout),
n=Fs();
int q=Fs();
for(int i=;i<n;i++){
int x=Fs(),y=Fs();
ll z=Fl();
link(x,y,z),
link(y,x,z);
}
dfs(fa[]=);
for(int i=;i<=n;i++)
f[i]=i;
for(int i=;i<=n;i++)
if(!(s[i]^)){
int y=bin(i);
int x=bin(fa[i]);
f[y]=x;
}
for(;q;q--){
ll v;
int x=Fs(),y,d;
if(x&){
x=Fs();
y=Fs();
x=bin(x);
y=bin(y);
v=Fl();
int l1=,l2=;
for(;x^y&&l1+l2<;)
dep[x]>dep[y]?
(s1[++l1]=s[x],
x=bin(fa[x])):
(s2[++l2]=s[y],
y=bin(fa[y]));
if(l1+l2>=)
puts("");
else{
for(int i=;i<=l1;i++)
v/=s1[i];
for(int i=l2;i>=;i--)
v/=s2[i];
printf("%I64d\n",v);
}
}
else{
d=Fs()<<;
v=Fl();
y=e[d].v;
x=fa[y];
fa[e[d-].v]^y
?:(d--,
y=e[d].v,
x=fa[y]);
s[y]=v;
if(!(s[y]^))
x=bin(x),
y=bin(y),
f[y]=x;
}
}
fclose(stdin),
fclose(stdout);
return ;
}