行走(walk.cpp/c/pas)

题目描述

“我有个愿望，我希望走到你身边。”

这是个奇异的世界，世界上的 n-1 条路联结起来形成一棵树，每条路有一个对应的权值 ci。

现在我会给出 q 组询问或操作。

每次询问我会从一个 x 点走到 y 点，初始在 x 点我会有一个数字 v，然后每走过一条权值为 c 的边，我的 v

就会变成\(\lfloor \frac vc \rfloor\) ,问最后到 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 6

1 2 1

1 3 7

1 4 4

2 5 5

2 6 2

1 4 6 17

2 3 2

1 4 6 17

1 5 5 20

2 4 1

1 5 1 3

样例输出 1

2

4

20

3

样例输入 2

5 4

1 2 7

1 3 3

3 4 2

3 5 5

1 4 2 100

1 5 4 1

2 2 2

1 1 3 4

样例输出 2

2

0

2

数据范围

对于 70%的数据保证\(1\le n\le 2000\)

对于 100%的数据保证\(1\le n \le 100000,1\le c_i\le 10^{18}\)

保证每次修改后的边权小于等于原来的边权且不会小于 1

分析

考场做法

如果走过的边权不是1，每次至少除2，只有\(log_2n\)次有效操作。直觉想法是把边权为1的边连接的点用并查集连起来，缩成一个等效点。

但这样做有一个问题，那就是向上跳可以直接跳fa，向下跳呢？于是我想出来用set维护边，给边附加一个maxdfn信息，然后二分查找，这样就不会被菊花图卡了。

然后觉得代码不止一点恶心，颓了半小时，终于狠下心来写完了，然后改了一会过了样例，简直不敢相信自己的眼睛。

时间复杂度\(O(n\log n+q\log v\log n)\)

#include<bits/stdc++.h>

#define co const

template<class T>T read(){

	T data=0,w=1;

	char ch=getchar();

	while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}

	while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();

	return data*w;

}

template<class T>T read(T&x){

	return x=read<T>();

}

typedef long long ll;

using namespace std;

co int N=1e5+1;

int n,m;

struct org_edge{int x,y;ll c;}oe[N]; // real

struct edge{ // vitual

	int mxp,to;ll c;

	bool operator<(co edge&e)co{

		return mxp!=e.mxp?mxp<e.mxp:to<e.to;

	}

};

set<edge> e[N];

typedef set<edge>::iterator it;

int dep[N],pos[N],dfn,fa[N][18];ll val[N];

void dfs(int x,int fa){ // real

	dep[x]=dep[fa]+1,pos[x]=++dfn,::fa[x][0]=fa;

	for(int i=1;i<=17;++i) ::fa[x][i]=::fa[::fa[x][i-1]][i-1];

	set<edge> s;

	for(it i=e[x].begin();i!=e[x].end();++i){

		int y=i->to;

		if(y==fa) {val[x]=i->c;continue;}

		dfs(y,x),s.insert((edge){dfn,y,i->c});

	}

	swap(e[x],s);

}

int lca(int x,int y){ // real

	if(dep[x]<dep[y]) swap(x,y);

	for(int i=17;i>=0;--i)

		if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];

	if(x==y) return x;

	for(int i=17;i>=0;--i)

		if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];

	return fa[x][0];

}

int pa[N];

int find(int x) {return x==pa[x]?x:pa[x]=find(pa[x]);}

void link(int x,int y){ // virtual

	assert(x==find(x)),assert(y==find(::fa[x][0]));

	pa[x]=y;

	it i=e[y].lower_bound((edge){pos[x],0,0});

	assert(pos[x]<=i->mxp),e[y].erase(i);

	for(i=e[x].begin();i!=e[x].end();++i) e[y].insert(*i);

	e[x].clear();

}

ll query(int x,int y,ll v){ // real->virtual

	int f=lca(x,y);

	x=find(x),y=find(y),f=find(f);

	for(;v&&x!=f;x=find(::fa[x][0])) v/=val[x];

	if(!v) return 0;

	assert(x==f);

	for(it i;v&&x!=y;x=i->to){

		i=e[x].lower_bound((edge){pos[y],0,0});

		v/=i->c;

	}

	return v;

}

void change(int p,ll c){ // real->virtual

	int x=find(oe[p].x),y=find(oe[p].y);

	if(x==y) return assert(c==1);

	if(dep[x]>dep[y]) swap(x,y);

	assert(x==find(::fa[y][0]));

	it i=e[x].lower_bound((edge){pos[y],0,0});

	assert(pos[y]<=i->mxp),e[x].erase(i),e[x].insert((edge){i->mxp,i->to,c}),val[y]=c;

	if(c==1) link(y,x);

}

int main(){

	freopen("walk.in","r",stdin),freopen("walk.out","w",stdout);

	read(n),read(m);

	for(int i=1;i<n;++i){

		read(oe[i].x),read(oe[i].y),read(oe[i].c);

		e[oe[i].x].insert((edge){0,oe[i].y,oe[i].c});

		e[oe[i].y].insert((edge){0,oe[i].x,oe[i].c});

	}

	dfs(1,0);

	for(int i=1;i<=n;++i) pa[i]=i;

	for(int i=1;i<=n;++i)if(val[i]==1) link(i,find(::fa[i][0]));

	while(m--){

		if(read<int>()==1){

			int x,y;ll v;

			read(x),read(y),read(v);

			printf("%lld\n",query(x,y,v));

		}

		else{

			int p;ll c;

			read(p),read(c);

			change(p,c);

		}

	}

	return 0;

}

刘哥做法

打表得到性质，下取整除法可以结合（意会），并且要证明的话是显然的。

于是树剖线段树维护路径乘积，维护一下溢出标记，然后每次把路径找出来就行了。

时间复杂度\(O(n+m\log^n)\)

#include<iostream>

#include<cstdio>

using namespace std;

typedef long long ll;

inline ll read()

{

	ll x=0,k=1;

	char ch=getchar();

	while(ch<'0'||ch>'9')

	{

		if(ch=='-') k=-1;

		ch=getchar();

	}

	while(ch>='0'&&ch<='9')

	{

		x=x*10+ch-'0';

		ch=getchar();

	}

	return k*x;

}

const int MAXN=2e5+10;

int n,Q;

int ecnt=0,head[MAXN],to[MAXN<<1],nx[MAXN<<1],fa[MAXN];

ll val[MAXN<<1],vf[MAXN];

int dep[MAXN];

int U[MAXN],V[MAXN];

inline void addedge(int u,int v,ll w)

{

	++ecnt;

	to[ecnt]=v;

	nx[ecnt]=head[u];

	val[ecnt]=w;

	head[u]=ecnt;

}

ll wp[MAXN];

int dfn[MAXN],dfnidx=0,rnk[MAXN],siz[MAXN],mxson[MAXN],top[MAXN];

void dfs1(int u,int f)

{

	fa[u]=f;

	siz[u]=1;

	dep[u]=dep[f]+1;

	for(int i=head[u]; i; i=nx[i])

	{

		int v=to[i];

		if(v==f)

			continue;

		dfs1(v,u);

		siz[u]+=siz[v];

		if(siz[v]>siz[mxson[u]])

			mxson[u]=v;

	}

}

void dfs2(int u,int tp)

{

	dfn[u]=++dfnidx;

	rnk[dfnidx]=u;

	top[u]=tp;

	if(mxson[u])

		dfs2(mxson[u],tp);

	for(int i=head[u]; i; i=nx[i])

	{

		int v=to[i];

		if(v!=mxson[u] && v!=fa[u])

			dfs2(v,v);

	}

}

ll prod[MAXN<<2];

#define root prod[o]

#define lson prod[o<<1]

#define rson prod[o<<1|1]

void pushup(int o)

{

	root=lson*rson;

	root=max(root,0LL);

}

void bd(int o,int l,int r)

{

	if(l==r)

	{

		root=wp[rnk[l]];

		return;

	}

	int mid=(l+r)>>1;

	bd(o<<1,l,mid);

	bd(o<<1|1,mid+1,r);

	pushup(o);

}

void update(int o,int l,int r,int pos,ll c)

{

	if(l==r)

	{

		root=c;

		return;

	}

	int mid=(l+r)>>1;

	if(pos<=mid)

		update(o<<1,l,mid,pos,c);

	else

		update(o<<1|1,mid+1,r,pos,c);

	pushup(o);

}

ll query(int o,int l,int r,int L,int R)

{

	ll res=1;

	if(l>R || L>r)

		return 1;

	if(L<=l && r<=R)

		return max(0LL,root);

	int mid=(l+r)>>1;

	if(L<=mid)

	{

		res*=query(o<<1,l,mid,L,R);

		res=max(res,0LL);

	}

	if(R>mid)

	{

		res*=query(o<<1|1,mid+1,r,L,R);

		res=max(res,0LL);

	}

	return res;

}

void solve()

{

	int idx=n;

	for(int i=1; i<n; ++i)

	{

		int u=read(),v=read();

		ll w=read();

		++idx;

		addedge(u,idx,0);

		addedge(idx,u,0);

		addedge(idx,v,0);

		addedge(v,idx,0);

		wp[idx]=w;

	}

	for(int i=1; i<=n; ++i)

		wp[i]=1;

	dfs1(1,0);

	dfs2(1,1);

	bd(1,1,idx);

	while(Q--)

	{

		int tp=read();

		if(tp==1)

		{

			int x=read(),y=read();

			ll v=read();

			while(top[x]!=top[y])

			{

				if(dep[top[x]]<dep[top[y]])

					swap(x,y);

				ll p=query(1,1,idx,dfn[top[x]],dfn[x]);

				if(p<=0)

				{

					puts("0");

					continue;

				}

				v/=p;

				x=fa[top[x]];

			}

			if(dep[x]<dep[y])

				swap(x,y);

			ll p=query(1,1,idx,dfn[y],dfn[x]);

			if(p<=0)

			{

				puts("0");

				continue;

			}

			v/=p;

			printf("%lld\n",v);

		}

		else

		{

			int p=read();

			ll c=read();

			update(1,1,idx,dfn[p+n],c);

		}

	}

}

void dfs(int u,int f)

{

	fa[u]=f;

	for(int i=head[u]; i; i=nx[i])

	{

		int v=to[i];

		if(v==f)

			continue;

		dep[v]=dep[u]+1;

		vf[v]=val[i];

		dfs(v,u);

	}

}

int bf()

{

	for(int i=1; i<n; ++i)

	{

		int u=read(),v=read();

		ll w=read();

		U[i]=u,V[i]=v;

		addedge(u,v,w);

		addedge(v,u,w);

	}

	dfs(1,0);

	while(Q--)

	{

		int tp=read();

		if(tp==1)

		{

			int x=read(),y=read();

			ll v=read();

			while(x!=y)

			{

				if(dep[x]>dep[y])

					v/=vf[x],x=fa[x];

				else

					v/=vf[y],y=fa[y];

			}

			printf("%lld\n",v);

		}

		else

		{

			int p=read();

			ll v=read();

			if(fa[U[p]]==V[p])

				vf[U[p]]=v;

			else

				vf[V[p]]=v;

		}

	}

	return 0;

}

int main()

{

	freopen("walk.in","r",stdin);

	freopen("walk.out","w",stdout);

	n=read();

	Q=read();

	if(n<=1000)

		return bf();

	solve();

	return 0;

}

std做法

其实往下跳没有必要了。过了lca以后仍然从另一边往上跳，溢出及时跳出就行了。这样也最多\(\log_2 v\)次

标程暂缺。陈年老题，估计也不会有了。

放上前辈的代码。

//QWsin

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

const int maxn=100000+10;

const int maxm=200000+10;

int n,Q;

int first[maxn],next[maxm],ecnt=0;

struct Edge{int u,v;ll w;Edge(int u=0,int v=0,ll w=0):u(u),v(v),w(w){}}e[maxm];

inline void add_edge(int u,int v,ll w)

{

	next[ecnt]=first[u];first[u]=ecnt;e[ecnt++]=Edge(u,v,w);

	next[ecnt]=first[v];first[v]=ecnt;e[ecnt++]=Edge(v,u,w);

}

int dep[maxn],fa[maxn],faid[maxn];

void dfs(int u,int pre,int deep)

{

	dep[u]=deep;

	for(int i=first[u];i!=-1;i=next[i])

		if(e[i].v!=pre)

		{

			fa[e[i].v]=u;faid[e[i].v]=i;

			dfs(e[i].v,u,deep+1);

		}

}

ll query(int a,int b,ll c)

{

	if(dep[a] > dep[b]) swap(a,b);

	if(dep[a] < dep[b]){

		for(;dep[a]<dep[b];b=fa[b])

			if((c/=e[faid[b]].w)==0) return 0;

	}

	if(a!=b)

	{

		for(;a!=b;a=fa[a],b=fa[b]){

			if((c/=e[faid[b]].w)==0) return 0;

			if((c/=e[faid[a]].w)==0) return 0;

		}

	}

	return c;

}

int main()

{

	freopen("walk.in","r",stdin);

	freopen("walk.out","w",stdout);

	cin>>n>>Q;ll w;

	memset(first,-1,sizeof first);

	for(int i=1,u,v;i<n;++i) {

		scanf("%d%d%lld",&u,&v,&w);add_edge(u,v,w);

	}

	dfs(1,1,1);

	int op,a,b;ll c;

	while(Q--)

	{

		scanf("%d",&op);

		if(op==1) {

			scanf("%d%d%lld",&a,&b,&c);

			printf("%lld\n",query(a,b,c));

		}

		else{

			scanf("%d%lld",&a,&c);

			e[a*2-1].w=e[a*2-2].w=c;

		}

	}

	return 0;

}

巴特西

test20190504 行走