Problem: maximinimax_flow (2016 finals)

You're given an undirected, connected graph with **N** nodes (numbered from 1
to **N**) and **N** edges. The **i**th edge connects distinct nodes **Ai** and
**Bi**, and has a capacity of **Ci**. No two edges directly connect the same
pair of nodes.

**M** operations will be performed on this graph, one after another. The nature of the **i**th operation is described by the value of **Oi**: 

\- If **Oi** = 1, then the **i**th operation is an update, in which the
capacity of the **Xi**th edge is changed to be **Yi**.

\- Otherwise, if **Oi** = 2, then the **i**th operation is a query, in which
you must determine the maximinimax flow in the graph after **Zi** edge
augmentations.

What do any of those terms mean? Let's define them:

\- An edge augmentation is a temporary increase of a certain edge's capacity
by 1 for the current query.

\- The max flow from node **u** to a different node **v** is the usual
definition of maximum flow in computer science (hopefully you're familiar with
it!), with node **u** being the source and node **v** being the sink. Each
edge may transport flow in either direction, so it may be thought of as two
directed edges (one in each direction), both with the same capacity.

\- The minimax flow in the graph is the smallest max flow value across all
pairs of distinct nodes. In other words, min{1 ≤ **u**, **v** ≤ **N**, **u** ≠
**v**} (F(**u**, **v**)), where F(**u**, **v**) is the max flow from node
**u** to node **v**.

\- The maximinimax flow in the graph after **x** edge augmentations is the
largest possible minimax flow which the graph can have after **x** optimal
edge augmentations are applied. Note that each edge can be augmented any non-
negative number of times (as long as the total number of augmentations in the
graph is **x**), and that the chosen edge augmentations are temporary — they
do not change the graph for future operations.

To reduce the size of the output, you should simply output one integer, the
sum of the answers to all of the queries.

### Input

Input begins with an integer **T**, the number of graphs. For each graph,
there is a first a line containing the space-separated integers **N** and
**M**. Then, **N** lines follow, the **i**th of which contains the space-
separated integers **Ai**, **Bi**, and **Ci**. Then, **M** lines follow, the
**i**th of which contains the space-separated integers **Oi**, **Xi**, and
**Yi** (if **Oi** = 1) or **Oi** and **Zi** (if **Oi** = 2).

### Output

For the **i**th graph, print a line containing "Case #**i**: " followed by the
sum of the answers to all queries on that graph.

### Constraints

1 ≤ **T** ≤ 85  
3 ≤ **N** ≤ 500,000  
1 ≤ **M** ≤ 500,000  
1 ≤ **Ai**, **Bi**, **Xi** ≤ **N**  
1 ≤ **Ci**, **Yi** ≤ 1,000,000  
0 ≤ **Zi** ≤ 1,000,000,000,000  
1 ≤ **Oi** ≤ 2  

### Explanation of Sample

In the first graph, the max flow between any two nodes is 10, so the minimax
flow is also 10. If we do no edge augmentations, then the maximinimax flow is
still 10. In the second graph, the maximinimax flow is initially 3, but is
then increased to 5 before the second query for a total of 8. In the third
graph, the maximinimax flow is initially 7 (between node 2 and any other
node). If we augment the edge from node 3 to node 2 twice, then the max flow
between node 2 and any other node is now 9. The max flow between any other
pair of nodes was already greater than 9, so the minimax flow is now 9. We
can't do any better than that, so the maximinimax flow is also 9.



Sample input:
5
3 1
1 2 5
1 3 5
2 3 5
2 0
3 3
1 2 3
1 3 2
2 3 1
2 0
1 3 3
2 0
4 1
3 1 6
3 2 7
3 4 5
1 4 8
2 2
4 1
3 1 6
3 2 7
3 4 5
1 4 8
2 5
7 9
1 2 15
2 3 8
2 4 9
3 5 18
4 5 11
4 6 17
6 7 22
2 4
2 5
2 11
1 2 12
2 11
1 1 12
1 5 5
2 11
2 55


Sample output:
Case #1: 10
Case #2: 8
Case #3: 9
Case #4: 11
Case #5: 123



Code: // MAXIMINIMAX FLOW
// Official Solution by Jacob Plachta

#define DEBUG 0

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x<0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x*x); }
string plural(string s) { return(Sz(s) && s[Sz(s)-1]=='x' ? s+"en" : s+"s"); }

const int INF = (int)1e9;
const LD EPS = 1e-9;
const LD PI = acos(-1.0);

//#if DEBUG
#define GETCHAR getchar
/*#else
#define GETCHAR getchar_unlocked
#endif*/

bool Read(int &x)
{
	char c,r=0,n=0;
	x=0;
		for(;;)
		{
			c=GETCHAR();
				if ((c<0) && (!r))
					return(0);
				if ((c=='-') && (!r))
					n=1;
				else
				if ((c>='0') && (c<='9'))
					x=x*10+c-'0',r=1;
				else
				if (r)
					break;
		}
		if (n)
			x=-x;
	return(1);
}

bool ReadLL(LL &x)
{
	char c,r=0,n=0;
	x=0;
		for(;;)
		{
			c=GETCHAR();
				if ((c<0) && (!r))
					return(0);
				if ((c=='-') && (!r))
					n=1;
				else
				if ((c>='0') && (c<='9'))
					x=x*10+c-'0',r=1;
				else
				if (r)
					break;
		}
		if (n)
			x=-x;
	return(1);
}

#define LIM 500005
#define LIM2 1000000

LL BLT[2][2][LIM2+1];

void Update(int a,int b,int i,int v)
{
	for (; i<=LIM2; i+=(i&-i))
		BLT[a][b][i]+=v;
}

void Update2(int a,int i,int v)
{
	Update(a,0,i,v);
	Update(a,1,i,i*v);
}

LL Query(int a,int b,LL ii)
{
	int i=(int)min(ii,(LL)LIM2);
	LL v=0;
		for(; i>0; i-=(i&-i))
			v+=BLT[a][b][i];
	return(v);
}

int main()
{
		if (DEBUG)
			freopen("in.txt","r",stdin);
	//vars
	int T,t;
	int N,M;
	int i,j,k;
	LL r1,r2,m,m2;
	LL tot,rem,cnt,sum;
	LL ans;
	static vector<PR> con[LIM];
	static int C[LIM],dep[LIM],cyc[LIM];
	static PR par[LIM];
	queue<int> Q;
	set<PR> S;
	set<PR>::iterator I;
	//testcase loop
	Read(T);
		Fox1(t,T)
		{
			//input
			Read(N),Read(M);
				Fox(i,N)
				{
					Read(j),Read(k),Read(C[i]);
					j--,k--;
					con[j].pb(mp(k,i));
					con[k].pb(mp(j,i));
				}
			//BFS to find the single cycle
			Fill(dep,-1);
			Q.push(0),dep[0]=0;
				for(;;)
				{
					i=Q.front(),Q.pop();
						Fox(j,Sz(con[i]))
							if ((k=con[i][j].x)!=par[i].x)
								if (dep[k]>=0)
									goto Done;
								else
									Q.push(k),dep[k]=dep[i]+1,par[k]=mp(i,con[i][j].y);
				}
			//retrace all edges in the cycle
Done:;
			Fill(cyc,0);
			cyc[con[i][j].y]=1;
				while (i!=k)
					if (dep[i]>dep[k])
					{
						cyc[par[i].y]=1;
						i=par[i].x;
					}
					else
					{
						cyc[par[k].y]=1;
						k=par[k].x;
					}
			//init BLTs
				Fox(i,N)
				{
					Update2(cyc[i],C[i],1);
						if (cyc[i])
							S.insert(mp(C[i],i));
				}
			//handle operations
			ans=0;
				while (M--)
				{
					Read(i);
						if (i==1)
						{
							//delete and re-add the adge
							Read(i),i--;
							Update2(cyc[i],C[i],-1);
								if (cyc[i])
									S.erase(mp(C[i],i));
							Read(C[i]);
							Update2(cyc[i],C[i],1);
								if (cyc[i])
									S.insert(mp(C[i],i));
						}
						else
						{
							//binary search on the answer
							ReadLL(tot);
							r1=1,r2=(LL)1e13;
								while (r2>r1)
								{
									m=(r1+r2+1)>>1;
									rem=tot;
									//non-cycle edges
									cnt=Query(0,0,m);
									sum=Query(0,1,m);
									rem-=cnt*m - sum;
										if (rem<0)
											goto Bad;
									//cycle edges
									I=S.begin(),i=I->x;
									I++,j=I->x;
										if (m<=(j<<1))
											rem-=max(0LL,m - (i+j));
										else
										{
											m2=(m+1)>>1;
											cnt=Query(1,0,m2);
											sum=Query(1,1,m2);
											rem-=cnt*m2 - sum;
												if (m&1)
													rem++;
										}
										if (rem<0)
										{
Bad:;
											r2=m-1;
											continue;
										}
									r1=m;
								}
							ans+=r1;
						}
				}
			//output
			printf("Case #%d: ",t);
			cout << ans << endl;
			//reset
				Fox(i,N)
					con[i].clear();
				while (!Q.empty())
					Q.pop();
			S.clear();
			Fill(BLT,0);
		}
	return(0);
}