首页 > 代码库 > NOIP模拟赛 行走
NOIP模拟赛 行走
题目描述
“我有个愿望，我希望走到你身边。”
这是个奇异的世界，世界上的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
6 61 2 11 3 71 4 42 5 52 6 21 4 6 172 3 21 4 6 171 5 5 202 4 11 5 1 3
样例输出1
24203
样例输入2
5 41 2 71 3 33 4 23 5 51 4 2 1001 5 4 12 2 21 1 3 4
样例输出2
202
数据范围
对于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 100001using namespace std;typedef long long ll;inline int Fs(){ int x=0,c=getchar(),f=1; for(;c<48||c>57;c=getchar()) if(!(c^45)) f=-1; for(;c>47&&c<58;c=getchar()) x=(x<<1)+(x<<3)+c-48; return x*f;}inline ll Fl(){ ll x=0,c=getchar(),f=1; for(;c<48||c>57;c=getchar()) if(!(c^45)) f=-1; for(;c>47&&c<58;c=getchar()) x=(x<<1)+(x<<3)+c-48; return x*f;}struct edge{ ll w; int v,nxt;}e[N<<1];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]+1, 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=1;i<n;i++){ int x=Fs(),y=Fs(); ll z=Fl(); link(x,y,z), link(y,x,z); } dfs(fa[1]=1); for(int i=1;i<=n;i++) f[i]=i; for(int i=1;i<=n;i++) if(!(s[i]^1)){ int y=bin(i); int x=bin(fa[i]); f[y]=x; } for(;q;q--){ ll v; int x=Fs(),y,d; if(x&1){ x=Fs(); y=Fs(); x=bin(x); y=bin(y); v=Fl(); int l1=0,l2=0; for(;x^y&&l1+l2<62;) dep[x]>dep[y]? (s1[++l1]=s[x], x=bin(fa[x])): (s2[++l2]=s[y], y=bin(fa[y])); if(l1+l2>=62) puts("0"); else{ for(int i=1;i<=l1;i++) v/=s1[i]; for(int i=l2;i>=1;i--) v/=s2[i]; printf("%I64d\n",v); } } else{ d=Fs()<<1; v=Fl(); y=e[d].v; x=fa[y]; fa[e[d-1].v]^y ?1:(d--, y=e[d].v, x=fa[y]); s[y]=v; if(!(s[y]^1)) x=bin(x), y=bin(y), f[y]=x; } } fclose(stdin), fclose(stdout); return 0;}
NOIP模拟赛 行走
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。