• 兩個數相加為偶數，只可能偶+偶/奇+奇，維護當前的奇偶數量，枚舉當前數，特判前一個數即可

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
int a[N];
signed main()
{
    int n,ans=0;
    cin >> n;
    for (int i = 1;i<=n;i++)
        cin >> a[i];
    int odd = 0, even = 0;
    for (int i = 1; i <= n;i++){
        if(a[i]&1){
            ans += odd;
            if(i>=2&&a[i-1]%2!=0)
                ans--;
        }else{
            ans += even;
            if(i>=2&&a[i-1]%2==0)
                ans--;
        }
		odd+=(a[i]&1);
		even+=(a[i]%2==0);
    }
    cout << ans;
}

• 當n為偶數時，所有格子都可以染色，不會沖突，連成環(huán)只有兩種情況，紅黃紅黃... 當為奇數時，有一個格子不能染色，先用前綴和維護兩種情況的總和，紅黃紅黃紅黃，以及黃紅黃紅黃紅，枚舉不能染色的格子，答案為前面的一種情況+后面的一種情況解決沖突，取max即可

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N], b[N], s1[N], s2[N];
int main()
{
    int n, ans = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i] >> b[i];
    if (n & 1)
    {
        for (int i = 1; i <= n; i++)
        {
            s1[i] += s1[i - 1] + (i & 1 ? a[i] : b[i]);
            s2[i] += s2[i - 1] + (i & 1 ? b[i] : a[i]);
        }

        for (int i = 1; i <= n; i++)
        {
            ans = max(ans, s1[i - 1] + s2[n] - s2[i]);
            ans = max(ans, s2[i - 1] + s1[n] - s1[i]);
        }

        cout << ans << endl;
    }
    else
    {
        int res = 0;
        for (int i = 1; i <= n; i++)
        {
            if (i & 1)
                res += a[i];
            else
                res += b[i];
        }
        int ans = res;
        res = 0;
        for (int i = 1; i <= n; i++)
        {
            if (i & 1)
                res += b[i];
            else
                res += a[i];
        }
        ans = max(ans, res);
        cout << ans << endl;
    }
}

• 首先dfs算出每個子樹的size，枚舉每個節(jié)點，計算出max-min即可

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
vector<int> g[N];
int sz[N], ans = 0;
int dfs(int x, int fa)
{
    sz[x] = 1;
    for (auto v : g[x])
    {
        if (v == fa)
            continue;
        dfs(v, x);
        sz[x] += sz[v];
    }
    int m1 = 0, m2 = 1e9;
    for (auto v : g[x])
    {
		if(v==fa) continue;
        m1 = max(m1, sz[v]);
        m2 = min(m2, sz[v]);
    }
	if(m2!=1e9)// 存在極值
    	ans += m1 - m2;
	return sz[x];
}
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, -1);
    cout << ans;
}