标签：树链剖分，线段树
题目
N<=1e5,M,Q<=2e5
保证询问中S,T不相等
分析
最大流就是最小割
对于M=N-1的情况，显然只需要割掉两点间权值最小的边
对于全部数据，我们发现每次最小割割掉的边只出现在
-
所有简单路径都包含的任何一条边
-
不同在两者间任意简单路径，但在一个环内的两条边
将每个环断成链后，用线段树维护，再将环缩点，做树链剖分
对于一次询问(S,T)，先求出LCA(S,T)
将其转化为两条路径，考虑一些特殊的情况
重链直接在树剖内查询，轻边在原本的线段树内查询
如果修改的是非环边，直接在树剖内单点修改
否则在一开始建出的线段树内修改，再修改这个环在树剖内对应节点的重儿子的权值
毒瘤题考码力，硬肝了5h才AC
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define dep(i,a,b) for(register int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define inf 0x7fffffff
using namespace std;
inline ll read()
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=1e5+6;
struct node{
node *lc,*rc;int lower;
void update(){lower=min(lc->lower,rc->lower);}
}pool[maxn<<2],*cur=pool;
struct SegTree{//线段树指针写法
node *root;int n;
void modify(node *u,int ul,int ur,int p,int k){
if(ul==ur){u->lower=k;return;}
int mid=(ul+ur)>>1;
if(p<=mid)modify(u->lc,ul,mid,p,k);else modify(u->rc,mid+1,ur,p,k);
u->update();
}
inline int query(node *u,int ul,int ur,int l,int r){
if(l<=ul&&ur<=r)return u->lower;
int mid=(ul+ur)>>1,re=inf;
if(l<=mid)re=min(re,query(u->lc,ul,mid,l,r));
if(r>mid)re=min(re,query(u->rc,mid+1,ur,l,r));
return re;
}
void build(node *&u,int ul,int ur,int *val){
u=cur++;
if(ul==ur){u->lower=val[ul];return;}
int mid=(ul+ur)>>1;
build(u->lc,ul,mid,val);
build(u->rc,mid+1,ur,val);
u->update();
}
void modify(int p,int k){modify(root,1,n,p,k);}
inline int query(int l,int r){return l>r?inf:query(root,1,n,l,r);}
void init(int _n,int *val){n=_n;build(root,1,n,val);}
}segt;
struct edge{int to,next,w;}e[maxn<<2];
int n,m,cnt,last[maxn],belong[maxn],st[maxn],id[maxn],num[maxn];
bool vis[maxn];int sta[maxn],len,idx,ori[maxn];
inline void insert(int u,int v,int w){e[++cnt]=(edge){v,last[u],w};last[u]=cnt;}
inline int calc(int u,int v){
if(u==v)return inf;
int sec=belong[u];
if(id[u]>id[v])swap(u,v);
return segt.query(id[u],id[v]-1)+min(segt.query(id[v],st[sec]+num[sec]-1),segt.query(st[sec],id[u]-1));
}
namespace tree{
SegTree segt_tree;
struct edge{int to,next,w,escape;}e[maxn<<1];
int n,cnt,idx,last[maxn],num[maxn],val[maxn],ori[maxn];
int dep[maxn],fa[maxn],top[maxn],pre[maxn],chain[maxn],dfn[maxn],heavy[maxn],pos[maxn];
inline void insert(int u,int v,int w,int o){e[++cnt]=(edge){v,last[u],w,o};last[u]=cnt;}
void dfs1(int u){
num[u]=1;
reg(u){
int &v=belong[e[i].to];
if(fa[u]==v)continue;
fa[v]=u,dep[v]=dep[u]+1;
top[v]=e[i].to,pre[v]=e[i].escape,val[v]=e[i].w;
dfs1(v);
num[u]+=num[v];
}
}
void dfs2(int u,int Fa){
pos[dfn[u]=++idx]=u,chain[u]=Fa;
reg(u){
int &v=belong[e[i].to];
if(v==fa[u])continue;
if(num[v]>num[heavy[u]])heavy[u]=v;
}
if(!heavy[u])return;
dfs2(heavy[u],Fa);
reg(u){
int &v=belong[e[i].to];
if(v==fa[u]||v==heavy[u])continue;
dfs2(v,v);
}
}
void init(){
dfs1(1);dfs2(1,1);
rep(i,1,n)
if(heavy[fa[i]]==i&&fa[i]!=1)ori[dfn[i]]=min(val[i],calc(pre[i],top[fa[i]]));
segt_tree.init(n,ori);
}
inline int getlca(int u,int v){
while(chain[u]!=chain[v]){
if(dep[chain[u]]>dep[chain[v]])swap(u,v);
v=fa[chain[v]];
}
if(dep[u]>dep[v])swap(u,v);
return u;
}
inline int getanc(int u,int Fa){
int now=0;
while(chain[u]!=chain[Fa])now=u,u=fa[chain[u]];
return u==Fa?chain[now]:pos[dfn[Fa]+1];
}
inline int chain_query(int u,int Fa){
int re=val[Fa];
while(chain[u]!=chain[Fa]){
re=min(min(re,calc(pre[chain[u]],top[fa[chain[u]]])),min(segt_tree.query(dfn[chain[u]]+1,dfn[u]),val[chain[u]]));
u=fa[chain[u]];
}
re=min(re,segt_tree.query(dfn[Fa]+1,dfn[u]));
return re;
}
inline int query(int u,int v){
int Fa=getlca(belong[u],belong[v]);
int u1=getanc(belong[u],Fa),v1=getanc(belong[v],Fa);
int re=calc((u1?pre[u1]:u),(v1?pre[v1]:v));
if(u1){
re=min(re,calc(u,top[belong[u]]));
re=min(re,chain_query(belong[u],u1));
}
if(v1){
re=min(re,calc(v,top[belong[v]]));
re=min(re,chain_query(belong[v],v1));
}
return re;
}
void modify(int u,int v,int w){
if(belong[u]==belong[v]){
int sec=belong[u];
if((id[u]+1-st[sec])%(::num[sec])!=(id[v]-st[sec]))swap(u,v);
segt.modify(id[u],w);
int &tmp=heavy[sec];
if(tmp&&fa[tmp]!=1)segt_tree.modify(dfn[tmp],min(val[tmp],calc(pre[tmp],top[fa[tmp]])));
}else{
u=belong[u],v=belong[v];
if(dep[u]>dep[v])swap(u,v);
val[v]=w;
if(heavy[u]==v&&u!=1)segt_tree.modify(dfn[v],min(val[v],calc(pre[v],top[fa[v]])));
}
}
}//树剖板子
void getcir(int u,int Fa){
vis[u]=true,sta[len++]=u;
reg(u){
int &v=e[i].to;
if(v==Fa)continue;
if(!vis[v]){
getcir(v,u);
if(belong[u]==belong[v])ori[id[v]]=e[i].w;
}else if(!belong[v]){
tree::n++;
while(1){
int tmp=sta[len-num[tree::n]-1];
belong[tmp]=tree::n,id[tmp]=++idx;
num[tree::n]++;
if(tmp==v)break;
}
ori[id[v]]=e[i].w;st[tree::n]=id[u];
}
}
if(!belong[u]){
st[++tree::n]=id[u]=++idx;
num[belong[u]=tree::n]=1;
}
len--;
}
void init(){
n=read();int m=read();
rep(i,1,m){
int u=read(),v=read(),w=read();
insert(u,v,w);insert(v,u,w);
}
getcir(1,0);segt.init(n,ori);
rep(u,1,n)
reg(u){
int &v=e[i].to;
if(belong[u]!=belong[v])tree::insert(belong[u],v,e[i].w,u);
}
tree::init();
}
void solve(){
int T=read();
while(T--){
int opt=read(),u=read(),v=read();
if(opt)tree::modify(e[u*2-1].to,e[u*2].to,v);else printf("%d\n",tree::query(u,v));
}
}
int main()
{
init();
solve();
return 0;
}
