行走(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 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
資料範圍
對于 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做法
//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;
}