maxkibble

template <typename T>
class flow_graph {
 public:
  static constexpr T eps = (T) 1e-9;
 
  struct edge {
    int from;
    int to;
    T c;
    T f;

maxkibble

// 两遍DFS,直径上的点保存在trace中

const int maxn = 1e5 + 5;

typedef pair<int, int> PII;

int n, pre[maxn], dis[maxn];
vector<PII> g[maxn];

void dfs(int x, int fa) {

maxkibble

int clk, dfu[maxn], low[maxn], sz, belong[maxn];
bool inStack[maxn];
std::stack<int> st;
std::vector<std::vector<int> > comp;

void tarjan(int u, int fa) {
    dfu[u] = low[u] = ++clk;
    st.push(u);
    inStack[u] = true;
    for (int v: g[u]) {

maxkibble

/*
Suppose graph is stored in a vector of vector...(g: std::vector<std::vector<int> >)
The graph has n nodes
The components are stored in variable: comp
belong[i] represents component ID for each node, start from 1
*/

int clk, dfu[maxn], low[maxn], sz, belong[maxn];
bool inStack[maxn];
std::stack<int> st;

maxkibble

void quickSort(int *a, int l, int r) {
	if (l >= r) return;
	// this is a good coding style to avoid overflow
	int mid = l + (r - l) / 2;
	// choose a[mid] as pivot to speed up for sequences in order
	int pivot = a[mid];
	std::swap(a[mid], a[r]);
	int i = l, j = r - 1;
	while (i <= j) {
		while (i <= j && a[i] <= pivot) i++;

maxkibble

from operator import add, sub, mul, truediv


class Calculator(object):
    op = {'+': add, '-': sub, '*': mul, '/': truediv}

    def to_suffix(self, s):
        st = []
        ret = ''
        tokens = s.split()

maxkibble

struct BinaryIndexedTree {
    int up;
    long long tree[maxn];
    
    void init(int u) {
        up = u;
        memset(tree, 0, sizeof(tree));
    }
    
    inline int lowbit(int x) { return (x & (-x)); }

maxkibble

const int maxn = 1e5 + 5;

struct Dsu {
	struct Node {
		int val, fa;
	} t[maxn];

	void init(int sz) {
		for (int i = 0; i < n; i++)
			t[i].val = 1, t[i].fa = i;

maxkibble

struct TrieNode {
	int minVal;
	TrieNode *child[2];
	TrieNode() {
		minVal = inf;
		child[0] = child[1] = NULL;
	}
};

struct Trie {

maxkibble

using std::vector;
using std::queue;

vector<int> topsort(const vector<vector<int> > &g) {
    int n = g.size();
    vector<int> d(n);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < g[i].size(); j++)
            d[g[i][j]]++;