Description：

给一个点仙人掌，支持修改边权，查询 $S\to T$ 的最大流。

$1\leqslant n\leqslant 2\times 10^5$

Solution：

首先既然是点仙人掌，那么就可以为每个环分配一个编号，每个点标记它属于哪个环，然后查询就是查询 $S$ 到 $T$ 路径上所有环和边能流过的最小流，显然在环上的流的大小是从两个方向走的最小值之和，然后有一个很神奇的操作是把一个环上的最小边拿出来删掉，然后把这个边权加到这个环的其他所有边上，然后直接查询链上最小值，会发现查询的就是答案，修改的话对于每种情况特判一下就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

int n,m,q;

#define MAXN 300010

#define MAXM 200010

struct edges

{

	int u,v,w;

}es[MAXM];

struct edge

{

	int to,nxt;

}e[MAXM << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

int dfn[MAXN],low[MAXN],tot = 0;

int stack[MAXN],top = 0;

int ins[MAXN],cir = 0;

vector<int> v;

void tarjan(int k)

{

	dfn[k] = low[k] = ++tot;

	stack[++top] = k;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(dfn[e[i].to] == 0)

		{

			tarjan(e[i].to);

			low[k] = min(low[k],low[e[i].to]);

			if(low[e[i].to] >= dfn[k])

			{

				int t;

				do

				{

					t = stack[top];--top;

					v.push_back(t);

				}while(t != e[i].to);

				v.push_back(k);

				if(v.size() != 2)

				{

					++cir;

					for(vector<int>::iterator it = v.begin();it != v.end();++it)ins[*it] = cir;

				}

				v.clear();

			}

		}

		else

		{

			low[k] = min(low[k],dfn[e[i].to]);

		}

	}

	return;

}

typedef long long ll;

struct node

{

	int c[2],fa;

	ll val,minv,tag;

	bool rev;

	node(){minv = val = 2147483647;tag = 0;}

}t[MAXN];

int id(int k){return (t[t[k].fa].c[0] == k ? 0 : 1);}

void maintain(int rt){t[rt].minv = min(t[rt].val,min(t[t[rt].c[0]].minv,t[t[rt].c[1]].minv));}

void pushdown(int rt)

{

	if(t[rt].rev)

	{

		t[t[rt].c[0]].rev ^= 1;t[t[rt].c[1]].rev ^= 1;

		swap(t[rt].c[0],t[rt].c[1]);t[rt].rev = false;

	}

	if(t[rt].tag)

	{

		t[t[rt].c[0]].minv += t[rt].tag;t[t[rt].c[0]].val += t[rt].tag;t[t[rt].c[0]].tag += t[rt].tag;

		t[t[rt].c[1]].minv += t[rt].tag;t[t[rt].c[1]].val += t[rt].tag;t[t[rt].c[1]].tag += t[rt].tag;

		t[rt].tag = 0;

	}

	return;

}

bool isroot(int k){return (t[t[k].fa].c[0] != k && t[t[k].fa].c[1] != k);}

void connect(int k,int f,int p){t[k].fa = f;t[f].c[p] = k;return;}

void rotate(int x)

{

	int y = t[x].fa,z = t[y].fa,fx = id(x),fy = id(y);

	if(!isroot(y))t[z].c[fy] = x;

	t[x].fa = z;

	connect(t[x].c[fx ^ 1],y,fx);

	connect(y,x,fx ^ 1);

	maintain(y);maintain(x);

	return;

}

void splay(int x)

{

	stack[++top] = x;

	for(int i = x;!isroot(i);i = t[i].fa)stack[++top] = t[i].fa;

	while(top)pushdown(stack[top--]);

	while(!isroot(x))

	{

		int y = t[x].fa;

		if(isroot(y)){rotate(x);break;}

		if(id(x) == id(y)){rotate(y);rotate(x);}

		else{rotate(x);rotate(x);}

	}

	return;

}

void access(int k){for(int i = 0;k;i = k,k = t[k].fa){splay(k);t[k].c[1] = i;maintain(k);}return;}

void makeroot(int k){access(k);splay(k);t[k].rev ^= 1;return;}

void link(int a,int b){makeroot(a);t[a].fa = b;return;}

void cut(int a,int b){makeroot(a);access(b);splay(b);t[a].fa = t[b].c[0] = 0;maintain(b);return;}

void add(int a,int b,int v)

{

	makeroot(a);access(b);splay(b);

	t[b].minv += v;t[b].tag += v;t[b].val += v;

	return;

}

struct heap

{

	priority_queue< pair<int,int> > ad,de;

	void insert(pair<int,int> v){ad.push(v);return;}

	void remove(pair<int,int> v){de.push(v);return;}

	pair<int,int> top()

	{

		while(!de.empty() && ad.top() == de.top())ad.pop(),de.pop();

		return ad.top();

	}

	void pop()

	{

		while(!de.empty() && ad.top() == de.top())ad.pop(),de.pop();

		ad.pop();

		return;

	}

}h[MAXN];

bool tag[MAXM];

int mine[MAXN];

int find(int x){access(x);splay(x);while(t[x].c[0])x = t[x].c[0];return x;}

int main()

{

	scanf("%d%d",&n,&m);

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

	{

		scanf("%d%d%d",&es[i].u,&es[i].v,&es[i].w);

		add(es[i].u,es[i].v);

	}

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

	{

		if(dfn[i] == 0)tarjan(i);

	}

	top = 0;

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

	{

		t[i + n].minv = t[i + n].val = es[i].w;

		if(ins[es[i].u] == 0 || ins[es[i].v] == 0 || ins[es[i].u] != ins[es[i].v])

		{

			link(es[i].u,i + n);link(es[i].v,i + n);

			continue;

		}

		h[ins[es[i].u]].insert(make_pair(-es[i].w,i));

	}

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

	{

		int v = h[i].top().second;

		tag[v] = true;

		mine[i] = v;

	}

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

	{

		if(!ins[es[i].u] || !ins[es[i].v] || ins[es[i].u] != ins[es[i].v] || tag[i])continue;

		link(es[i].u,i + n);link(es[i].v,i + n);

	}

	for(int i = 1;i <= cir;++i)add(es[mine[i]].u,es[mine[i]].v,es[mine[i]].w);

	scanf("%d",&q);

	int opt,a,b;

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

	{

		scanf("%d%d%d",&opt,&a,&b);

		if(opt == 0)

		{

			makeroot(a);access(b);splay(b);

			printf("%d\n",t[b].minv);

		}

		else

		{

			int vu = ins[es[a].u],vv = ins[es[a].v];

			if(!vu || !vv || vu != vv)

			{

				makeroot(a + n);splay(a + n);

				t[a + n].val = b;

				maintain(a + n);

			}

			else

			{

				int v = vu;

				h[v].remove(make_pair(-es[a].w,a));

				h[v].insert(make_pair(-b,a));

				access(a + n);splay(a + n);t[a + n].val += b - es[a].w;maintain(a + n);

				int p = h[v].top().second;

				if(h[v].top().second == mine[v])

				{

					if(a == mine[v])

					{

						add(es[a].u,es[a].v,-es[a].w);

						add(es[a].u,es[a].v,b);

					}

				}

				else

				{

					add(es[mine[v]].u,es[mine[v]].v,-es[mine[v]].w);

					cut(es[p].u,p + n);cut(es[p].v,p + n);

					link(es[mine[v]].u,mine[v] + n);link(es[mine[v]].v,mine[v] + n);

					es[a].w = b;

					add(es[p].u,es[p].v,es[p].w);

					mine[v] = p;

				}

				es[a].w = b;

			}

		}

	}

	return 0;

}