题意：
给你n个点和n-1条边组成的一棵树，按顺序给出数的每一条边。
询问m次，每次给出一个x求x除以从点a到点b所有边的权值和的乘积，还有修改，给出边的编号，修改某条边的权值。
思路：
树链剖分，用点的编号建立线段树，当然一开始要记录第几条边的两个端点各是什么，便于修改的时候进行查询。
重点是用深度较大的那个点记录两个点之间的权值。
查询的时候当两者重链的top相等的时候注意去掉top点的权值。
然后这道题每条边的权值都是在10^18以内，所以如果线段树某个元素代表的权值之乘积大于1e18的话就直接标记成0或者别的。
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int n,m;
long long ttmp[];
long long INF=1e18;
struct bian
{
int a,b;
long long c;
};
bian bians[];
struct edge
{
int id;
long long num;
edge *next;
};
edge edges[<<];
edge *adj[];
int ednum;
inline void addEdge(int a,int b,long long c)
{
edge *tmp;
tmp=&edges[ednum++];
tmp->id=b;
tmp->num=c;
tmp->next=adj[a];
adj[a]=tmp;
}
int fa[],top[],son[],siz[],id[],fid[],dep[];
bool vis[];
void dfs1(int me,int deep)
{
int maxsiz=-;
vis[me]=;
dep[me]=deep;
siz[me]=;
for(edge *it=adj[me];it;it=it->next)
{
if(!vis[it->id])
{
fa[it->id]=me;
dfs1(it->id,deep+);
if(maxsiz<siz[it->id])
{
maxsiz=siz[it->id];
son[me]=it->id;
}
siz[me]+=siz[it->id];
}
}
}
int num;
void dfs2(int me,int t)
{
vis[me]=;
top[me]=t;
id[me]=++num;
fid[num]=me;
if(son[me])
{
dfs2(son[me],t);
}
for(edge *it=adj[me];it;it=it->next)
{
if(!vis[it->id])
{
dfs2(it->id,it->id);
}
}
}
struct tr
{
int s,e;
long long num;
};
tr tree[<<];
long long mul(long long aaa,long long bbb)
{
if(aaa==||bbb==)
return ;
if(INF/aaa<bbb)
{
return ;
}
else
return aaa*bbb;
}
void build(int k,int s,int e)
{
tree[k].s=s;
tree[k].e=e;
if(s==e)
{
tree[k].num=ttmp[fid[s]];
return;
}
int mid=(s+e)>>;
build(k<<,s,mid);
build(k<<|,mid+,e);
tree[k].num=mul(tree[k<<].num,tree[k<<|].num);
}
long long ans;
void qsum(int k,int s,int e)
{
if(tree[k].s==s&&tree[k].e==e)
{
if(fid[s]==)
return;
ans=mul(ans,tree[k].num);
return;
}
int mid=(tree[k].s+tree[k].e)>>;
if(e<=mid)
{
qsum(k<<,s,e);
}
else if(s>mid)
{
qsum(k<<|,s,e);
}
else
{
qsum(k<<,s,mid);
qsum(k<<|,mid+,e);
}
} inline void print(int a,int b,long long c)
{
ans=;
int f1=top[a],f2=top[b];
while(f1!=f2)
{
if(dep[f1]<dep[f2])
{
swap(f1,f2);
swap(a,b);
}
qsum(,id[f1],id[a]);
a=fa[f1];
f1=top[a];
}
if(dep[a]>dep[b])
{
swap(a,b);
}
if(id[a]+<=id[b])
{
qsum(,id[a]+,id[b]);
}
if(ans==)
printf("0\n");
else
printf("%I64d\n",c/ans);
}
void updat(int k,int tar,long long c)
{
if(tree[k].s==tree[k].e)
{
tree[k].num=c;
return;
}
int mid=(tree[k].s+tree[k].e)>>;
if(tar<=mid)
{
updat(k<<,tar,c);
}
else
{
updat(k<<|,tar,c);
}
tree[k].num=mul(tree[k<<].num,tree[k<<|].num);
}
int main()
{
num=;
memset(vis,,sizeof(vis));
memset(son,,sizeof(son));
ednum=;
scanf("%d%d",&n,&m);
for(int i=;i<n;i++)
{
int a,b;
scanf("%d%d%I64d",&a,&b,&bians[i].c);
bians[i].a=a;
bians[i].b=b;
addEdge(a,b,bians[i].c);
addEdge(b,a,bians[i].c);
}
fa[]=;
dfs1(,);
memset(vis,,sizeof(vis));
dfs2(,);
for(int i=;i<n;i++)
{
if(dep[bians[i].a]>dep[bians[i].b])
{
ttmp[bians[i].a]=bians[i].c;
}
else
{
ttmp[bians[i].b]=bians[i].c;
}
}
build(,,n);
for(int i=;i<=m;i++)
{
int typ,a,b;
long long c;
scanf("%d",&typ);
if(typ==)
{
scanf("%d%d%I64d",&a,&b,&c);
print(a,b,c);
}
else
{
scanf("%d%I64d",&a,&c);
if(dep[bians[a].a]<dep[bians[a].b])
{
updat(,id[bians[a].b],c);
}
else
{
updat(,id[bians[a].a],c);
}
}
}
}