1. Prefix Sum Algorithm

---

Example 1: Interstellar Cake Problem

Approach: Brute Force to Prefix Sum + Binary Search Optimization

#include <algorithm>
#include <iostream>
using namespace std;
int result;
const int N = 200005;
long long n, q, arr[N], countFactor[N], prefixSum[N], x;

int main()
{
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &arr[i]);
        countFactor[i] = 1;
        while (!(arr[i] & 1))
        {
            arr[i] >>= 1;
            countFactor[i] <<= 1;
        }
        prefixSum[i] = prefixSum[i - 1] + countFactor[i];
    }
    scanf("%lld", &q);
    while (q--)
    {
        scanf("%lld", &x);
        int pos = (lower_bound(prefixSum + 1, prefixSum + 1 + n, x) - prefixSum);
        printf("%d\n", arr[pos]);
    }
}

Tips:

1. Prefix sums, difference arrays, and loop indices should start from 1
2. When dividing a whole into parts and calculating the sum of a certain interval, use the prefix sum approach
3. C++ STL binary search function: lower_bound
4. Two Pointers Algorithm

---

Example 1: Permutation Sorting

Approach: Two Pointers for Single Sequence (Fast and Slow Pointers)

Technique: Since this problem involves a sequence from 1 to n in ascending order, the array indices correspond to the element values. (The index of number 1 is 1, the index of number 2 is 2, and so on.)

#include <algorithm>
#include <iostream>
using namespace std;
int n, T, arr[1000005], maxVal, operations;
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        operations = 0;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
            scanf("%d", &arr[i]);
        int i = 1;
        while (i <= n)
        {
            if (arr[i] == i)
                i++;
            else
            {
                int maxVal = arr[i];
                int j = i + 1;
                maxVal = max(maxVal, arr[j]);
                while (maxVal > j)
                {
                    j++;
                    maxVal = max(maxVal, arr[j]);
                }
                operations += j - i + 1;
                i = j + 1;
            }
        }
        printf("%d\n", operations);
    }
    return 0;
}

3. Interval Merging

---

Example 1: Burning Red Cliffs

Approach 1: Interval Merging

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
typedef pair<long long, long long> pll;
int n;
vector<pll> segments;
long long totalLength;

void mergeIntervals(vector<pll> &segs)
{
    vector<pll> result;
    sort(segs.begin(), segs.end());
    long long start = -2e31, end = -2e31;
    for (auto seg : segs)
        if (end < seg.first)
        {
            if (start != -2e31)
                result.push_back({start, end});
            start = seg.first, end = seg.second;
        }
        else
            end = max(end, seg.second);
    if (start != -2e31)
        result.push_back({start, end});
    segs = result;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        long long l, r;
        scanf("%lld%lld", &l, &r);
        segments.push_back({l, r});
    }
    mergeIntervals(segments);
    for (auto seg : segments)
        totalLength += seg.second - seg.first;
    printf("%lld", totalLength);
    return 0;
}

Approach 2: Discretization + Difference Array

Approach:

1. The problem has a large data range but few intervals - use discretization
2. The problem can be transformed into adding 1 to all numbers in [l, r] for each interval. Then determine how many points are not 0 in the final state. However, direct simulation would be too slow, so we use difference arrays after discretization, then calculate prefix sums.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
typedef pair<int, int> pii;
int n, total = 0;
const int N = 4e4 + 5;
int diff[N], prefix[N];
vector<int> allValues;
vector<pii> intervals;
vector<pii> queries;

int find(int x)
{
    int l = 0, r = allValues.size() - 1;
    while (l < r)
    {
        int mid = (l + r) / 2;
        if (allValues[mid] >= x)
            r = mid;
        else
            l = mid + 1;
    }
    return r + 1;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        queries.push_back({l, r});
        allValues.push_back(l);
        allValues.push_back(r);
    }
    sort(allValues.begin(), allValues.end());
    allValues.erase(unique(allValues.begin(), allValues.end()), allValues.end());
    
    for (auto item : queries)
    {
        int l = find(item.first), r = find(item.second);
        diff[l]++, diff[r]--;
    }
    
    for (int i = 1; i <= allValues.size(); i++)
        prefix[i] += prefix[i - 1] + diff[i];
    
    int start, end;
    for (int i = 1; i <= allValues.size(); i++)
    {
        if (prefix[i] != 0 && prefix[i - 1] == 0)
            start = i - 1;
        if (prefix[i] == 0 && prefix[i - 1] != 0)
        {
            end = i - 1;
            total += allValues[end] - allValues[start];
        }
    }
    printf("%d", total);
    return 0;
}

4. Linked Lists

---

Example 1: Elimination Game

Approach: Doubly Linked List for Fast Deletion Operations

#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e6 + 10;
char s[N];
vector<int> toRemove, nextRound;
int prevNode[N], nextNode[N];
bool removed[N];

void markForRemoval(int k)
{
    if (!removed[k])
    {
        removed[k] = true;
        toRemove.push_back(k);
    }
}

void processRound()
{
    toRemove.clear();
    for (int k : nextRound)
    {
        int a = prevNode[k], b = k, c = nextNode[k];
        if (s[a] == s[b] && s[b] != s[c] && s[c] != '#')
        {
            markForRemoval(b);
            markForRemoval(c);
        }
        else if (s[a] != s[b] && s[b] == s[c] && s[a] != '#')
        {
            markForRemoval(a);
            markForRemoval(b);
        }
    }
}

int main()
{
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    s[0] = s[n + 1] = '#';
    for (int i = 1; i <= n; i++)
    {
        prevNode[i] = i - 1, nextNode[i] = i + 1;
        nextRound.push_back(i);
    }
    prevNode[0] = 1, nextNode[n + 1] = n;
    
    while (true)
    {
        processRound();
        if (toRemove.empty())
            break;
        nextRound.clear();
        for (int k : toRemove)
        {
            int a = prevNode[k], b = k, c = nextNode[k];
            if (!removed[a] && a && (nextRound.empty() || a != nextRound.back()))
                nextRound.push_back(a);
            if (!removed[c] && c != n + 1)
                nextRound.push_back(c);
            nextNode[a] = c, prevNode[c] = a;
        }
    }
    
    if (nextNode[0] == n + 1)
        puts("EMPTY");
    else
    {
        for (int i = nextNode[0]; i != n + 1; i = nextNode[i])
            printf("%c", s[i]);
    }
    return 0;
}

Example 2: Nearest Value

Approach: Doubly Linked List for Fast Deletion Operations

Approach:

1. Find the number with the smallest difference to A[i] - use sorting (after sorting, the numbers immediate before and after A[i] have the smallest differences)
2. Start enumerating from the nth number and output in reverse order - because the problem asks for the number before A[i] with smallest difference, and all numbers are before n, so order is not a concern
3. After enumerating the nth number, delete it and continue moving forward

#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
typedef pair<long long, int> pli;
int n;
int positions[N], prevNode[N], nextNode[N];
pli values[N], results[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> values[i].first;
        values[i].second = i;
    }
    sort(values + 1, values + 1 + n);
    
    for (int i = 1; i <= n; i++)
    {
        prevNode[i] = i - 1, nextNode[i] = i + 1;
        positions[values[i].second] = i;
    }
    
    values[0].first = -4e9, values[n + 1].first = 4e9;
    
    for (int i = n; i > 1; i--)
    {
        int current = positions[i], left = prevNode[current], right = nextNode[current];
        long long leftDiff = abs(values[left].first - values[current].first);
        long long rightDiff = abs(values[right].first - values[current].first);
        
        if (leftDiff <= rightDiff)
            results[i] = {leftDiff, values[left].second};
        else
            results[i] = {rightDiff, values[right].second};
            
        nextNode[left] = right, prevNode[right] = left;
    }
    
    for (int i = 2; i <= n; i++)
        cout << results[i].first << ' ' << results[i].second << endl;
    return 0;
}

5. Stacks

---

Example 1: Bracket Painter

Approach: Using Stack for Bracket Matching

Technique: Bracket sequences often utilize the stack data structure

#include <algorithm>
#include <cstring>
#include <iostream>
#include <stack>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int maxLength = 0;
    string str;
    cin >> str;
    stack<int> stk;
    for (int i = 0; i < str.size(); i++)
    {
        char c = str[i];
        if (stk.size())
        {
            char top = str[stk.top()];
            if (c == ')' && top == '(' || c == ']' && top == '[' || c == '}' && top == '{')
                stk.pop();
            else
                stk.push(i);
        }
        else
            stk.push(i);
            
        if (stk.size())
            maxLength = max(maxLength, i - stk.top());
        else
            maxLength = max(maxLength, i + 1);
    }
    cout << maxLength << endl;
    return 0;
}

Example 2: Deletion (Remove Specified Substring from String)

Approach: Stack - only used for operations at the end

#include <algorithm>
#include <cstring>
#include <iostream>
#include <stack>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s, t;
    cin >> s >> t;
    string stack;
    for(char c : s)
    {
        stack += c;
        while(stack.size() >= t.size() && stack.substr(stack.size() - t.size()) == t)
            stack.erase(stack.end() - t.size(), stack.end());
    }
    cout << stack << endl;
    return 0;
}

Example 3: Largest Rectangle in Histogram

Approach: Monotonic Stack - find the nearest number to the left (right) that is larger (smaller) than the current number

#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
typedef long long ll;
int n;
int heights[N], leftBounds[N], rightBounds[N], stack[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (scanf("%d", &n), n)
    {
        for (int i = 1; i <= n; i++)
            scanf("%d", &heights[i]);
        heights[0] = heights[n + 1] = -1;
        int top = 0;
        stack[0] = 0;
        
        for (int i = 1; i <= n; i++)
        {
            while (top && heights[i] <= heights[stack[top]])
                top--;
            leftBounds[i] = stack[top];
            stack[++top] = i;
        }
        
        top = 0;
        stack[0] = n + 1;
        
        for (int i = n; i > 0; i--)
        {
            while (top && heights[i] <= heights[stack[top]])
                top--;
            rightBounds[i] = stack[top];
            stack[++top] = i;
        }
        
        ll maxArea = 0;
        for (int i = 1; i <= n; i++)
            maxArea = max(maxArea, (ll)heights[i] * (rightBounds[i] - leftBounds[i] - 1));
        printf("%lld\n", maxArea);
    }
    return 0;
}

Example 4: City Game

Approach: Simulation/Dynamic Programming + Monotonic Stack

Approach: This problem is an enhanced version of Example 3. The model can be abstracted to Example 3 (see diagram below).

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1e3 + 10;
int n, m;
int grid[N][N], leftBounds[N], rightBounds[N], stack[N];
int calculateMax(int h[])
{
    h[0] = h[m + 1] = -1;
    int top = 0;
    stack[0] = 0;
    
    for (int i = 1; i <= m; i++)
    {
        while (top && h[i] <= h[stack[top]])
            top--;
        leftBounds[i] = stack[top];
        stack[++top] = i;
    }
    
    top = 0;
    stack[0] = m + 1;
    
    for (int i = m; i > 0; i--)
    {
        while (top && h[i] <= h[stack[top]])
            top--;
        rightBounds[i] = stack[top];
        stack[++top] = i;
    }
    
    int maxArea = 0;
    for (int i = 1; i <= m; i++)
        maxArea = max(maxArea, h[i] * (rightBounds[i] - leftBounds[i] - 1));
    return maxArea;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            char c;
            cin >> c;
            if (c == 'F')
                grid[i][j] = grid[i - 1][j] + 1;
        }
    
    int result = 0;
    for (int i = 1; i <= n; i++)
        result = max(result, calculateMax(grid[i]));
    
    cout << 3 * result << endl;
    return 0;
}

6. Queues

---

Example 1: Machine Translation

Approach: Queue - First-In-First-Out (FIFO)

#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
const int N = 1e3 + 10;
int n, m;
int result = 0;
bool inQueue[N];
queue<int> q;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> m >> n;
    while (n--)
    {
        int x;
        cin >> x;
        if (!inQueue[x])
        {
            if (q.size() == m)
            {
                inQueue[q.front()] = false;
                q.pop();
            }
            q.push(x);
            inQueue[x] = true;
            result++;
        }
    }
    cout << result << endl;
    return 0;
}

Example 2: Sliding Window

Approach: Monotonic Queue

#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int n, m;
int arr[N], window[N];
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    
    int head = 0, tail = -1;
    for (int i = 0; i < n; i++)
    {
        while (head <= tail && window[head] < i - m + 1)
            head++;
        while (head <= tail && arr[window[tail]] >= arr[i])
            tail--;
        window[++tail] = i;
        if (i >= m - 1)
            cout << arr[window[head]] << " ";
    }
    puts("");
    
    head = 0, tail = -1;
    for (int i = 0; i < n; i++)
    {
        while (head <= tail && window[head] < i - m + 1)
            head++;
        while (head <= tail && arr[window[tail]] <= arr[i])
            tail--;
        window[++tail] = i;
        if (i >= m - 1)
            cout << arr[window[head]] << " ";
    }
    return 0;
}

Example 3: Bus Transfer

Approach: Sliding Window + Queue Simulation

Approach:

We can scan each record from front to back while maintaining a queue that represents the valid time range (45 minutes) for using coupons:

1. If the current record is a bus ride, add it to the maintained coupon interval;
2. If the current record is a train ride, scan through all coupons in the queue to find the first unused one that is greater than or equal to the current price;
3. We can use a boolean array to check for duplicate coupons to ensure each coupon is used at most once.

#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n;
int result = 0;
struct Ticket
{
    int time, price;
    bool used;
} queue[N];

int main()
{
    scanf("%d", &n);
    int left = 0, right = 0;
    for (int i = 0; i < n; i++)
    {
        int type, price, time;
        scanf("%d%d%d", &type, &price, &time);
        if (type == 0)
        {
            result += price;
            queue[right++] = {time, price};
        }
        else
        {
            while (left <= right && time - queue[left].time > 45)
                left++;
            bool found = false;
            for (int j = left; j <= right; j++)
            {
                if (queue[j].used == false && queue[j].price >= price)
                {
                    queue[j].used = true;
                    found = true;
                    break;
                }
            }
            if (!found)
                result += price;
        }
    }
    printf("%d\n", result);
    return 0;
}

Example 4: Submatrix

Approach: Two-Dimensional Sliding Window

Approach: A two-dimensional monotonic queue is equivalent to finding the minimum/maximum value in a one-dimensional case for each row.

Step 1: For each row, find the minimum/maximum value in a window of size b Step 2: On the basis of step 1, for each column, find the minimum/maximum value in a window of size a (which can be understood as height)

#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e3 + 10, mod = 998244353;
typedef long long ll;
int n, m, a, b;
int matrix[N][N], rowMax[N][N], rowMin[N][N], window[N];
int result = 0;

void getMax(int input[], int output[], int size, int k)
{
    int head = 0, tail = -1;
    for (int i = 0; i < size; i++)
    {
        while (head <= tail && window[head] <= i - k)
            head++;
        while (head <= tail && input[window[tail]] <= input[i])
            tail--;
        window[++tail] = i;
        output[i] = input[window[head]];
    }
}

void getMin(int input[], int output[], int size, int k)
{
    int head = 0, tail = -1;
    for (int i = 0; i < size; i++)
    {
        while (head <= tail && window[head] <= i - k)
            head++;
        while (head <= tail && input[window[tail]] >= input[i])
            tail--;
        window[++tail] = i;
        output[i] = input[window[head]];
    }
}

int main()
{
    cin >> n >> m >> a >> b;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> matrix[i][j];
    
    for (int i = 0; i < n; i++)
    {
        getMax(matrix[i], rowMax[i], m, b);
        getMin(matrix[i], rowMin[i], m, b);
    }
    
    int tempA[N], tempB[N], tempC[N];
    for (int i = b - 1; i < m; i++)
    {
        for (int j = 0; j < n; j++)
            tempA[j] = rowMax[j][i];
        getMax(tempA, tempB, n, a);
        
        for (int j = 0; j < n; j++)
            tempA[j] = rowMin[j][i];
        getMin(tempA, tempC, n, a);
        
        for (int j = a - 1; j < n; j++)
            result = (result + (ll)tempB[j] * tempC[j]) % mod;
    }
    
    cout << result << endl;
    return 0;
}

7. KMP Algorithm

---

Example 1: Period

Approach: Calculate the next array - minimum period t = n - next[n]

#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int n;
char pattern[N];
int nextArray[N];

int main()
{
    int T = 1;
    while (scanf("%d", &n), n)
    {
        scanf("%s", pattern + 1);
        for (int i = 2, j = 0; i <= n; i++)
        {
            while (j && pattern[i] != pattern[j + 1])
                j = nextArray[j];
            if (pattern[i] == pattern[j + 1])
                j++;
            nextArray[i] = j;
        }
        printf("Test case #%d\n", T++);
        for (int i = 1; i <= n; i++)
        {
            int period = i - nextArray[i];
            if (i % period == 0 && i / period > 1)
                printf("%d %d\n", i, i / period);
        }
        puts("");
    }
    return 0;
}

Example 2: Find String

Approach: Use the next array to find all prefixes that equal suffixes in a string

Approach:

1. If l1 = next[i] is the longest common prefix and suffix, then the second longest is l2 = next[l1], the third longest is l3 = next[l2], and so on. This way we can find all common prefixes and suffixes in the string.
2. Store all next[i] in a boolean array, then find the first number that appears before. This is our answer.

If the length of this string is also marked, it means it meets the requirements. If not valid, find the longest common prefix and suffix of the current longest common prefix and suffix. This longest common prefix and suffix will appear before and in the middle.

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
char pattern[N];
int nextArray[N];
bool exists[N];

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%s", pattern + 1);
        int length = strlen(pattern + 1);
        
        for (int i = 2, j = 0; i <= length; i++)
        {
            while (j && pattern[i] != pattern[j + 1])
                j = nextArray[j];
            if (pattern[i] == pattern[j + 1])
                j++;
            nextArray[i] = j;
        }
        
        for (int i = 0; i <= length; i++)
            exists[i] = false;
            
        for (int i = 1; i < length; i++)
            exists[nextArray[i]] = true;
            
        int result = 0;
        for (int i = nextArray[length]; i; i = nextArray[i])
            if (exists[i])
            {
                result = i;
                break;
            }
                
        if (!result)
            puts("not exist");
        else 
        {
            pattern[result + 1] = 0;
            printf("%s\n", pattern + 1);
        }
    }
    return 0;
}

8. Trie Trees (Prefix Trees)

---

Generally, in Trie problems, the characters are either all lowercase letters, all uppercase letters, all digits, or just 0 and 1. In other words, the number of characters is not large.

Mainly used for prefix problems.

insert (insertion)

When we need to insert a string s, we start with a pointer p pointing to the root node.

Then, we scan each character c in s in order. When we finish scanning all characters in s, we mark that p is the end of a string.

Example 1: Prefix Statistics

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int children[N][26];
int countEnd[N];
char input[N];
int nodeCount;

void insert(char *str)
{
    int current = 0;
    for (int i = 0; str[i]; i++)
    {
        int index = str[i] - 'a';
        if (!children[current][index])
            children[current][index] = ++nodeCount;
        current = children[current][index];
    }
    countEnd[current]++;
}

int query(char *str)
{
    int current = 0, result = 0;
    for (int i = 0; str[i]; i++)
    {
        int index = str[i] - 'a';
        if (!children[current][index])
            return result;
        current = children[current][index];
        result += countEnd[current];
    }
    return result;
}

int main()
{
    scanf("%d%d", &n, &m);
    while (n--)
    {
        scanf("%s", input);
        insert(input);
    }
    while (m--)
    {
        scanf("%s", input);
        printf("%d\n", query(input));
    }
    return 0;
}

Example 2: Phone List

Approach:

1. First store each number digit by digit, incrementing for each digit
2. Check if any number has all digits appearing more than once, indicating it's a prefix of another number, output "NO"

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
typedef long long ll;
int n, m;
int children[N][10];
int countEnd[N];
char numbers[N][10];
int nodeCount;

void insert(char *num)
{
    int current = 0;
    for (int i = 0; num[i]; i++)
    {
        int index = num[i] - '0';
        if (!children[current][index])
            children[current][index] = ++nodeCount;
        current = children[current][index];
        countEnd[current]++;
    }
}

bool check(char *num)
{
    int current = 0;
    for (int i = 0; num[i]; i++)
    {
        int index = num[i] - '0';
        if (countEnd[children[current][index]] == 1)
            return true;
        current = children[current][index];
    }
    return false;
}

int main()
{
    scanf("%d", &n);
    while (n--)
    {
        int flag = 0;
        nodeCount = 0;
        memset(children[0], 0, sizeof children);
        memset(countEnd, 0, sizeof countEnd);
        scanf("%d", &m);
        for (int i = 0; i < m; i++)
        {
            scanf("%s", numbers[i]);
            insert(numbers[i]);
        }
        for (int i = 0; i < m; i++)
        {
            if (!check(numbers[i]))
            {
                flag = 1;
                break;
            }
        }
        if (flag == 1)
            puts("NO");
        else
            puts("YES");
    }
    return 0;
}

Example 3: Encrypted Information

Approach: This problem is a combination of Example 1 and Example 2 (N strings stored in Trie, M strings are query strings)

1. When M string is longer than N strings, use the approach from Example 1 to count all prefix occurrences
2. When M string is shorter than N strings, use the approach from Example 2

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 500010;
int n, m;
int children[N][2];
int countEnd[N], passCount[N];
char input[N][10];
int nodeCount;

void insert(string s)
{
    int current = 0;
    for (int i = 0; s[i]; i++)
    {
        int index = s[i] - '0';
        if (!children[current][index])
            children[current][index] = ++nodeCount;
        current = children[current][index];
        passCount[current]++;
    }
    countEnd[current]++;
}

int query(string s)
{
    int current = 0, result = 0;
    for (int i = 0; s[i]; i++)
    {
        int index = s[i] - '0';
        if (!children[current][index])
            return result;
        current = children[current][index];
        result += countEnd[current];
    }
    return result + passCount[current] - countEnd[current];
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        int k;
        string s;
        cin >> k;
        for (int j = 1; j <= k; j++)
        {
            char c;
            cin >> c;
            s += c;
        }
        insert(s);
    }
    for (int i = 1; i <= m; i++)
    {
        int k;
        string s;
        cin >> k;
        for (int j = 1; j <= k; j++)
        {
            char c;
            cin >> c;
            s += c;
        }
        printf("%d\n", query(s));
    }
    return 0;
}

9. Union-Find

---

Example 1: Smooth Project

Approach: Use Union-Find to maintain multiple sets. If two elements are not in the same set, add them to the same set to form a connected component. The answer is (number of connected components - 1).

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 10010;
int n, m;
int parent[N];

int find(int x)
{
    if(parent[x] != x)
        parent[x] = find(parent[x]);
    return parent[x];
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        parent[i] = i;
    int components = n;
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if(find(a) != find(b))
        {
            parent[find(a)] = find(b);
            components--;
        }
    }
    printf("%d", components - 1);
    return 0;
}

10. Heaps (Binary Tree Structure)

---

Example 1: Exercise Book

Approach: Min-Heap

Approach:

1. Implement deletion of any element - use a heap
2. Students always choose the cheapest exercise book - use a min-heap

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int N = 2e5 + 10;
typedef pair<int, int> pii;
int n, m;
int prices[N];
priority_queue<pii, vector<pii>, greater<pii>> minHeaps[3];
bool purchased[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &prices[i]);
    for (int j = 0; j < 2; j++)
        for (int i = 0; i < n; i++)
        {
            int type;
            scanf("%d", &type);
            minHeaps[type - 1].push({prices[i], i});
        }
    scanf("%d", &m);
    while (m--)
    {
        int category;
        scanf("%d", &category);
        category--;
        while (minHeaps[category].size() && purchased[minHeaps[category].top().second])
            minHeaps[category].pop();
        if (minHeaps[category].empty())
            printf("-1 ");
        else
        {
            auto book = minHeaps[category].top();
            minHeaps[category].pop();
            printf("%d ", book.first);
            purchased[book.second] = true;
        }
    }
    return 0;
}

Example 2: Median in Data Stream

Approach: Dynamic Median - Two-Pile Heap

Approach:

1. Max-heap: maintains the maximum value in the smaller part of the set.
2. Min-heap: maintains the minimum value in the larger part of the set.

If the sizes of the two heaps differ by no more than 1, the top of the larger heap must be the median (when there's an even number of elements, the median is one of the two middle values after sorting).

class Solution
{
public:
    priority_queue<int, vector<int>, greater<int>> minHeap;
    // Min-heap: maintains the minimum value in the larger part of the set
    priority_queue<int> maxHeap; // Max-heap: maintains the maximum value in the smaller part of the set
    
    void insert(int num)
    {
        maxHeap.push(num); // First add all inserted numbers to the max-heap, then exchange
        if (minHeap.size() && maxHeap.top() > minHeap.top())
        { // If the top of the max-heap > top of the min-heap, exchange the two numbers
            int maxVal = maxHeap.top(), minVal = minHeap.top();
            maxHeap.pop(), minHeap.pop();
            maxHeap.push(minVal), minHeap.push(maxVal);
        }
        if (maxHeap.size() > minHeap.size() + 1)
        { // If the sizes differ by more than 1, move the top of the max-heap to the top of the min-heap
            minHeap.push(maxHeap.top());
            maxHeap.pop();
        }
    }

    double getMedian()
    {
        if (maxHeap.size() + minHeap.size() & 1)
            return maxHeap.top();
        return (maxHeap.top() + minHeap.top()) / 2.0;
    }
};

Example 3: Load Balancing

Approach: Min-Heap

Understanding: Let the start time of the ith task be a[i], only tasks with end time before a[i] affect whether the computing power is sufficient.

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 200010;
int n, m;
int power[N];
priority_queue<PII, vector<PII>, greater<PII> > taskQueue[N];
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++ i)scanf("%d",&power[i]);
    while (m -- ){
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        while(taskQueue[b].size()&&taskQueue[b].top().x<=a){
            power[b] += taskQueue[b].top().y;
            taskQueue[b].pop();
        }
        if(power[b]<d)puts("-1");
        else{
            taskQueue[b].push({a+c,d});
            power[b] -= d;
            printf("%d\n",power[b]);
        }
    }
    return 0;
}

11. Hash Tables

---

Example 1: Equal Sums

Approach: Fast completion of add, delete, modify, and search operations - use hash tables

Approach:

1. First calculate the sum of each sequence, then enumerate all possible sums after removing each number, store them in a hash table
2. If two different sequences have the same sum, output the answer

#include <algorithm>
#include <iostream>
#include <unordered_map>
using namespace std;
const int N = 2e5 + 10;
typedef long long ll;
typedef pair<int, int> pii;
int numbers[N];

int main()
{
    int n;
    scanf("%d", &n);
    unordered_map<int, pii> sumMap;
    for (int i = 1; i <= n; i++)
    {
        int m, sum = 0;
        scanf("%d", &m);
        for (int j = 1; j <= m; j++)
        {
            scanf("%d", &numbers[j]);
            sum += numbers[j];
        }
        for (int j = 1; j <= m; j++)
        {
            int target = sum - numbers[j];
            if (sumMap.count(target) && sumMap[target].first != i)
            {
                puts("YES");
                printf("%d %d\n", sumMap[target].first, sumMap[target].second);
                printf("%d %d\n", i, j);
                return 0;
            }
            sumMap[target] = {i, j};
        }
    }
    puts("NO");
    return 0;
}

12. DFS

---

Example 1: Count

Approach: Brute force enumeration (TLE) - use DFS

Approach: Search each digit of the number, only 4 and 7 are options

#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
int n;
int result;

void dfs(ll current)
{
    if (current > n)
        return;
    if (current)
        result++;
    dfs(current * 10 + 4);
    dfs(current * 10 + 7);
}

int main()
{
    scanf("%d", &n);
    dfs(0);
    printf("%d", result);
    return 0;
}

Example 2: Horseshoe

#include <algorithm>
#include <iostream>
using namespace std;
const int N = 5;
int n;
int result;
char grid[N][N];
bool visited[N][N];

void dfs(int x, int y, int left, int right)
{
    visited[x][y] = true;
    if (left == right)
    {
        result = max(result, left + right);
        visited[x][y] = false;
        return;
    }
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    for (int i = 0; i < 4; i++)
    {
        int a = x + dx[i], b = y + dy[i];
        if (a >= 0 && a < n && b >= 0 && b < n && !visited[a][b])
        {
            if (grid[x][y] == ')' && grid[a][b] == '(')
                continue;
            if (grid[a][b] == '(')
                dfs(a, b, left + 1, right);
            else
                dfs(a, b, left, right + 1);
        }
    }
    visited[x][y] = false;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%s", grid[i]);
    if (grid[0][0] == '(')
        dfs(0, 0, 1, 0);
    printf("%d", result);
    return 0;
}

Example 3: Simple Sudoku

Method 1: Pruning (low time complexity)

#include <algorithm>
#include <iostream>
using namespace std;
const int N = 10;
typedef long long ll;
char grid[N][N];
bool row[N][N], col[N][N], cell[3][3][N];
bool dfs(int x, int y)
{
    if (y == 9)
        x++, y = 0;
    if (x == 9)
    {
         for (int i = 0; i < 9; i++)
            cout << grid[i] << endl;
        return true;
    }
       
    if (grid[x][y] != '.')
       return dfs(x, y + 1);
    for (int i = 0; i < 9; i++)
    {
        if (!row[x][i] && !col[y][i] && !cell[x / 3][y / 3][i])
        {
            grid[x][y] = i + '1';
            row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = true;
            if(dfs(x, y + 1)) return true;
            grid[x][y] = '.';
            row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = false;
        }
    }
    return false;
}

int main()
{
    for (int i = 0; i < 9; i++)
    {
        cin >> grid[i];
        for (int j = 0; j < 9; j++)
        {
            if (grid[i][j] != '.')
            {
                int t = grid[i][j] - '1';
                row[i][t] = col[j][t] = cell[i / 3][j / 3][t] = true;
            }
        }
    }
    dfs(0, 0);
    return 0;
}

Method 2: Without Pruning (high time complexity)

bool dfs(int x, int y)
{
    if (y == 9) x ++, y = 0;
    if (x == 9)
    {
        for (int i = 0; i < 9; i ++ ) cout << grid[i] << endl;
        return true;
    }

    if (grid[x][y] != '.') return dfs(x, y + 1);

    for (int i = 0; i < 9; i ++ )
        if (!row[x][i] && !col[y][i] && !cell[x / 3][y / 3][i])
        {
            grid[x][y] = i + '1';
            row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = true;
            dfs(x, y + 1);
            row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = false;
            grid[x][y] = '.';
        }
}

Tips: When changing to void type, there's no output. The reason is:

Error code: dfs(x, y+1) --- if the current position is a number, we directly search forward, and cannot execute the following for loop to asign values to that number, otherwise it would change the original value at that position, and no result would be found.

In other words, when changed to bool type, when g[x][y] != '.', it directly calls dfs(x, y + 1) without executing the following for loop. But with void type, after dfs(x, y + 1), the following for loop is still executed, which changes the original value at that position.

13. BFS

---

Example 1: Flowers for Algernon

Approach: Find shortest path - use BFS

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 210;
typedef pair<int, int> pii;
int n, m, rows, cols;
char grid[N][N];
int distance[N][N];
pii queue[N * N];
int startX, startY;

int bfs()
{
    int head = 0, tail = 0;
    queue[0] = {startX, startY};
    memset(distance, -1, sizeof distance);
    distance[startX][startY] = 0;
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    while (head <= tail)
    {
        auto current = queue[head++];
        for (int i = 0; i < 4; i++)
        {
            int x = current.first + dx[i], y = current.second + dy[i];
            if (x >= 0 && x < rows && y >= 0 && y < cols && grid[x][y] != '#' && distance[x][y] == -1)
            {
                distance[x][y] = distance[current.first][current.second] + 1;
                if (grid[x][y] == 'E')
                    return distance[x][y];
                queue[++tail] = {x, y};
            }
        }
    }
    return -1;
}

int main()
{
    cin >> n;
    while (n--)
    {
        cin >> rows >> cols;
        for (int i = 0; i < rows; i++)
            for (int j = 0; j < cols; j++)
            {
                cin >> grid[i][j];
                if (grid[i][j] == 'S')
                    startX = i, startY = j;
            }
        int steps = bfs();
        if (steps == -1)
            cout << "oop!" << endl;
        else
            cout << steps << endl;
    }
    return 0;
}

14. Tree and Graph Traversal

---

Example 1: Tree Height

#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int maxHeight = 0;
int graph[N], edges[N * 2], nextEdge[N * 2], edgeCount, distances[N];
bool visited[N];

void addEdge(int a, int b)
{
    edges[edgeCount] = b, nextEdge[edgeCount] = graph[a], graph[a] = edgeCount++;
}

void dfs(int node)
{
    visited[node] = true;
    maxHeight = max(maxHeight, distances[node]);
    for (int i = graph[node]; i != -1; i = nextEdge[i])
    {
        int neighbor = edges[i];
        if (!visited[neighbor])
        {
            distances[neighbor] = distances[node] + 1;
            dfs(neighbor);
        }
    }
}

int main()
{
    edgeCount = 0;
    memset(graph, -1, sizeof graph);
    cin >> n >> m;
    distances[m] = 0;
    for (int i = 0; i < n - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        addEdge(a, b), addEdge(b, a);
    }
    dfs(m);
    cout << maxHeight << endl;
    return 0;
}

15. Topological Sorting

---

Tips: Directed Acyclic Graph Topological Order

Example 1: Queuing

Approach:

1. Each requirement contains two integers a,b, indicating that child a should be before child b. --- use topological sorting
2. When multiple valid queuing orders exist, the child with the smaller number should be as far forward as possible. --- use priority queue

#include <algorithm>
#include <iostream>
using namespace std;
const int N = 510, M = 5010;
int n, m;
int graph[N], edges[M], nextEdge[M], edgeCount, inDegree[N];

void addEdge(int a, int b)
{
    edges[edgeCount] = b, nextEdge[edgeCount] = graph[a], graph[a] = edgeCount++;
}

void topologicalSort()
{
    priority_queue<int, vector<int>, greater<int>> heap;
    for (int i = 1; i <= n; i++)
        if (!inDegree[i])
            heap.push(i);
        while (heap.size())
        {
            auto current = heap.top();
            printf("%d ", current);
            heap.pop();
            for (int i = graph[current]; i != -1; i = nextEdge[i])
            {
                int neighbor = edges[i];
                if (--inDegree[neighbor] == 0)
                    heap.push(neighbor);
            }
        }
}

int main()
{
    cin >> n >> m;
    memset(graph,-1,sizeof graph);
    while (m--)
    {
        int a, b;
        cin >> a >> b;
        inDegree[b]++;
        addEdge(a, b);
    }
    topologicalSort();
    return 0;
}

16. Shortest Paths

---

Example 1: Dijkstra Sequence

Approach: Naive Dijkstra

#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int graph[N][N], distances[N];
bool visited[N];
int sequence[N];
bool dijkstra()
{
    memset(distances, 0x3f, sizeof distances);
    memset(visited,0,sizeof visited);
    distances[sequence[0]] = 0;
    for (int i = 0; i < n;i++)
    {
        int current = sequence[i];
        for (int j = 1; j <= n;j++)
        {
            if(!visited[j]&&distances[current]>distances[j])
                return false;
        }
        for (int j = 1; j <= n;j++)
            distances[j] = min(distances[j], distances[current] + graph[current][j]);
        visited[current] = true;
    }
    return true;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(graph,0x3f,sizeof graph);
    while (m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        graph[a][b] = graph[b][a] = c;
    }
    int k;
    scanf("%d", &k);
    while(k--)
    {
        for (int i = 0; i < n;i++)
            scanf("%d", &sequence[i]);
        if(dijkstra())
            puts("Yes");
        else
            puts("No");
    }
    return 0;
}

Example 2: Shortest Path

Approach: SPFA

#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
const int N = 1e5 + 10, M = 2e5 + 10;
typedef long long ll;
int n, m;
int graph[N], weights[M], edges[M], nextEdge[M], edgeCount;
int predecessors[N];
bool visited[N];
ll distances[N];
int path[N];

void addEdge(int a, int b, int c)
{
    edges[edgeCount] = b, weights[edgeCount] = c, nextEdge[edgeCount] = graph[a], graph[a] = edgeCount++;
}

void spfa()
{
    memset(distances, 0x3f, sizeof distances);
    memset(predecessors, -1, sizeof predecessors);
    distances[1] = 0;
    queue<int> q;
    q.push(1);
    visited[1] = true;
    while (q.size())
    {
        auto current = q.front();
        q.pop();
        visited[current] = false;
        for (int i = graph[current]; i != -1; i = nextEdge[i])
        {
            int neighbor = edges[i];
            if (distances[neighbor] > distances[current] + weights[i])
            {
                distances[neighbor] = distances[current] + weights[i];
                predecessors[neighbor] = current;
                if (!visited[neighbor])
                {
                    q.push(neighbor);
                    visited[neighbor] = true;
                }
            }
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(graph,-1,sizeof graph);
    while (m--)
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        addEdge(a, b, w), addEdge(b, a, w);
    }
    spfa();
    if (predecessors[n] == -1)
        puts("-1");
    else
    {
        int pathLength = 0;
        for (int i = n; i != -1; i = predecessors[i])
            path[pathLength++] = i;
        for (int i = pathLength - 1; i >= 0; i--)
            printf("%d ", path[i]);
    }
    return 0;
}

Example 3: Shortest Distance

Approach: Super Source + Heap-Optimized Dijkstra

Super source and super sink are virtual points often used in graphs for:

1. Multiple source points and multiple sink points - create a super source and super sink
2. Multiple source points and one sink point - create a super source
3. One source point and multiple sink points - create a super sink

Approach:

1. This is a problem with multiple source points for shortest paths - use Dijkstra for each source point (TLE)
2. Optimization: Add a new point (super source), connect the super source to all stores with edges of weight 0, then perform single-source shortest paths from the super source.

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int N = 1e5 + 10, M = 3e5 + 10;
typedef pair<int, int> pii;
int n, m;
int graph[N], weights[M], edges[M], nextEdge[M], edgeCount;
bool visited[N];
int distances[N];

void addEdge(int a, int b, int c)
{
    edges[edgeCount] = b, weights[edgeCount] = c, nextEdge[edgeCount] = graph[a], graph[a] = edgeCount++;
}

void dijkstra()
{
    memset(distances, 0x3f, sizeof distances);
    distances[0] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> heap;
    heap.push({0, 0});
    while(heap.size())
    {
        auto current = heap.top();
        heap.pop();
        int node = current.second, dist = current.first;
        if(visited[node])
            continue;
        visited[node] = true;
        for (int i = graph[node]; i != -1;i=nextEdge[i])
        {
            int neighbor = edges[i];
            if(distances[neighbor]>dist+weights[i])
            {
                distances[neighbor] = dist + weights[i];
                heap.push({distances[neighbor], neighbor});
            }
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(graph,-1,sizeof graph);
    while (m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        addEdge(a, b, c), addEdge(b, a, c);
    }
    int k;
    scanf("%d",&k);
    while (k--)
    {
        int x;
        scanf("%d", &x);
        addEdge(0, x, 0);
    }
    dijkstra();
    int q;
    scanf("%d",&q);
    while(q--)
    {
        int y;
        scanf("%d", &y);
        printf("%d\n", distances[y]);
    }
    return 0;
}

Example 4: Sum of Shortest Paths

Approach: Floyd

Technique: Deleting a point in a graph is difficult. Think inversely - add points one by one to the graph. Each time, use Floyd with the ith point as the intermediate point. Finally, calculate the sum of distances between all pairs of added points.

#include <algorithm>
#include <iostream>
using namespace std;
const int N = 510;
typedef long long ll;
int n;
bool inGraph[N];
int distances[N][N];
int points[N];
ll results[N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            scanf("%d", &distances[i][j]);
    for (int i = 1; i <= n;i++)
        scanf("%d", &points[i]);
    
    for (int u = n; u > 0;u--)
    {
        int current = points[u];
        inGraph[current] = true;
        for (int i = 1; i <= n;i++)//floyd
            for (int j = 1; j <= n;j++)
                distances[i][j] = min(distances[i][j], distances[i][current] + distances[current][j]);
        for (int i = 1; i <= n;i++)
            for (int j = 1; j <= n;j++)
            if(inGraph[i]&&inGraph[j])
                results[u] += distances[i][j];
    }
    for (int i = 1; i <= n;i++)
            printf("%lld ", results[i]);
    return 0;
}

17. Minimum Spanning Trees

---

Example 1: Corridor Sprinkler Festival

Approach: Kruskal

Approach: Use Kruskal's algorithm to build a minimum spanning tree

#include <algorithm>
#include <iostream>
using namespace std;
const int N = 6010;
int n, m;
int parent[N], size[N];
struct Edge
{
    int a, b, weight;
    bool operator < (const Edge &other) const
    {
        return weight < other.weight;
    }
} edges[N];

int find(int x)
{
    if (parent[x] != x)
        parent[x] = find(parent[x]);
    return parent[x];
}

int kruskal()
{
    sort(edges, edges + n - 1);
    for (int i = 1; i <= n; i++)
        parent[i] = i, size[i] = 1;
    int total = 0;
    for (int i = 0; i < n - 1; i++)
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].weight;
        a = find(a), b = find(b);
        if (a != b)
        {
            parent[a] = b;
            total += (size[a] * size[b] - 1) * (w + 1);
            size[b] += size[a];
        }
    }
    return total;
}

int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d", &n);
        for (int i = 0; i < n - 1; i++)
        {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            edges[i] = {x, y, z};
        }
        printf("%d\n", kruskal());
    }
    return 0;
}

Example 2: City Power Supply

18. Bipartite Graphs

---

Example 1: Imprisoning Criminals

Approach: Coloring Method to Determine Bipartite Graph

Approach:

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 20010, M = 200010;
int n, m;
int graph[N], edges[M], nextEdge[M], weights[M], edgeCount;
int colors[N];
void addEdge(int a, int b, int c)
{
    edges[edgeCount] = b, weights[edgeCount] = c, nextEdge[edgeCount] = graph[a], graph[a] = edgeCount++;
}

bool dfs(int node, int color, int limit)
{
    colors[node] = color;
    for (int i = graph[node]; i != -1;i=nextEdge[i])
    {
        if(weights[i]<=limit)
            continue;
        int neighbor = edges[i];
        if(colors[neighbor]==-1)
        {
            if(!dfs(neighbor,!color,limit))
                return false;
        }
        else if (colors[neighbor]==color)
            return false;
    }
    return true;
}

bool check(int limit)
{
    memset(colors, -1, sizeof colors);
    bool valid = true;
    for (int i = 1; i <= n;i++)
    {
        if(colors[i]==-1)
        if(!dfs(i,0,limit))
        {
            valid = false;
            break;
        }
    }
    return valid;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(graph, -1, sizeof graph);
    while (m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        addEdge(a, b, c), addEdge(b, a, c);
    }
    int left = 0, right = 1e9;
    while (left < right)
    {
        int mid = left + right >> 1;
        if(check(mid))
            right = mid;
        else
            left = mid + 1;
    }
    printf("%d", left);
    return 0;
}

Example 2: Tree Edge Addition

Approach: Coloring Method to Determine Bipartite Graph (all trees are bipartite graphs)

#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e5+10, M = 2*N;
typedef long long ll;
int n, m;
int graph[N], edges[M], nextEdge[M], edgeCount;
void addEdge(int a, int b)
{
    edges[edgeCount] = b, nextEdge[edgeCount] = graph[a], graph[a] = edgeCount++;
}

void dfs(int node, int color, int parent)
{
    if (!color)
        m++;
    for (int i = graph[node]; i != -1; i = nextEdge[i])
    {
        int neighbor = edges[i];
        if(neighbor==parent)
            continue;
        dfs(neighbor, !color, node);
    }
}

int main()
{
    scanf("%d", &n);
    memset( graph, -1, sizeof graph );
    for (int i = 1; i <= n - 1; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        addEdge(a, b), addEdge(b, a);
    }
    dfs(1, 0, 0);
    printf("%lld", (ll)m * (n - m) - (n - 1));
    return 0;
}

Example 3: Perfect Barn

Approach: Maximum Matching Problem - Hungarian Algorithm

#include <algorithm>
#include <iostream>
using namespace std;
const int N = 40010;
int n, m;
int graph[N], edges[N], nextEdge[N], edgeCount;
int matches[N];
bool visited[N];
void addEdge(int a, int b)
{
    edges[edgeCount] = b, nextEdge[edgeCount] = graph[a], graph[a] = edgeCount++;
}

bool findMatch(int x)
{
    for (int i = graph[x]; i != -1;i=nextEdge[i])
    {
        int j = edges[i];
        if(!visited[j])
        {
            visited[j] = true;
            if(matches[j]==0||findMatch(matches[j]))
            {
                matches[j] = x;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(graph, -1, sizeof(graph));
    for (int i = 1; i <= n; i++)
    {
        int count;
        scanf("%d", &count);
        while (count--)
        {
            int x;
            scanf("%d", &x);
            add(i, x);
        }
    }
    int result = 0;
    for (int i = 1; i <= n;i++)
    {
        memset(visited, false, sizeof visited);
        if(findMatch(i))
            result++;
    }
    printf("%d", result);
    return 0;
}