猜到思路dp【N】【3】，以及背包10优化为差，选一半。但是终究不会实现，请看vcr；但是从子树大小的奇数偶数考虑还是没想到

#include <bits/stdc++.h>
using namespace std;

#define int long long 

const int INF = 0x3f3f3f3f3f3f3f3f; 
const int N = 100050;

vector<int> g[N]; 
int p[N];   
int c[N];    
int dp[N][3]; 
                  // dp[u][0] - 以u为根的子树中0比1多时的最小代价
                  // dp[u][1] - 以u为根的子树中1比0多时的最小代价
                  // dp[u][2] - 以u为根的子树中0和1数量相等时的最小代价
int son[N];        // 记录每个节点的子树大小（包含自身）

void dfs(int u) {
    dp[u][0] = dp[u][1] = dp[u][2] = INF;
    son[u] = 1; 
    int sz = 1;  // 记录奇数大小的子树数量（包括自己）
    int sum = (c[u] ? 0 : p[u]);  // 基础代价：如果当前节点是0，加上它的价格

    vector<int> vec;  // 存储各个子树的代价差
    vec.push_back((c[u] ? p[u] : -p[u]));  // 当前节点的贡献

    for (auto v : g[u]) {
        dfs(v);
        son[u] += son[v];

        if (son[v] % 2 == 0) { 
            sum += dp[v][2];    // 直接使用平衡状态的代价
        } else {                // 子树大小为奇数
            ++sz;               // 奇数子树计数增加
            sum += dp[v][1];
            vec.push_back(dp[v][0] - dp[v][1]);  // 记录选择0较多的代价差
        }
    }

    sort(vec.begin(), vec.end());

    if (son[u] % 2 == 0) {  // 当前子树大小为偶数
        // 选择前sz/2个最小的代价差来平衡0和1的数量
        for (int i = 0; i < sz / 2; ++i) sum += vec[i];
        dp[u][2] = sum;  // 平衡状态的结果
    } else {             // 当前子树大小为奇数
        // 情况1：1比0多（选择前sz/2个最小的代价差）
        for (int i = 0; i < sz / 2; ++i) sum += vec[i];
        dp[u][1] = sum;

        // 情况2：0比1多（多选一个代价差）
        dp[u][0] = sum + vec[sz / 2];
    }
}

signed main() {  
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n;
    cin >> n;

    for (int i = 1; i <= n; ++i) {
        int k;
        cin >> c[i] >> p[i] >> k;
        while (k--) {
            int v;
            cin >> v;
            g[i].push_back(v);
        }
    }

    dfs(1);

    if (n & 1) cout << min(dp[1][0], dp[1][1]);
    else cout << dp[1][2];

    return 0;
}

二叉树数据结构题

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+1;
struct no{
    int win,lose;
}tr[N<<2];
int k;

bool solve(int u){
    if(u>=(1<<k)){
        return true;
    }else if(tr[u].lose>tr[u].win) return false;

    tr[u<<1].win=tr[u].win;
    tr[u<<1|1].win=tr[u].lose;
    if(solve(u<<1)&&solve(u<<1|1)){
        return true;
    }
    swap(tr[u<<1].win,tr[u<<1|1].win);
    return solve(u<<1)&&solve(u<<1|1);
}

signed main(){
    cin>>k;
    for(int i=k;i>=1;i--){
        for(int j=(1<<(i-1));j<(1<<i);j++){
            cin>>tr[j].lose;
        }
    }
    cin>>tr[1].win;
    if(solve(1)){
        for(int i=(1<<(k-1));i<(1<<k);i++){
            cout<<tr[i].win<<" ";
            cout<<tr[i].lose;
            if(i!=(1<<k)) cout<<" ";
        }
    }else{
        cout<<"No Solution";
    }
    return 0;
}

小贪心

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
vector<int> adj[N];
int parent[N];
int depth[N];
bool visited[N];

void dfs(int u, int fa) {
    for (int v : adj[u]) {
        if (v == fa) continue;
        parent[v] = u;
        depth[v] = depth[u] + 1;
        dfs(v, u);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    int root = -1;
    for (int i = 1; i <= n; ++i) {
        int p;
        cin >> p;
        if (p == -1) {
            root = i;
        } else {
            adj[i].push_back(p);
            adj[p].push_back(i);
        }
    }

    parent[root] = -1;
    depth[root] = 0;
    dfs(root, -1);

    int total_edges = 0;
    int max_depth = 0;
    while (m--) {
        int x;
        cin >> x;
        int current = x;
        while (current != root && !visited[current]) {
            visited[current] = true;
            total_edges++;
            current = parent[current];
        }
        max_depth = max(max_depth, depth[x]);
        cout << 2 * total_edges - max_depth << '\n';
    }

    return 0;
}

模拟+输出格式

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<pair<string, string>> intervals;

    for(int i = 0; i < n; i++) {
        string start, hyphen, end;
        cin >> start >> hyphen >> end;
        intervals.push_back({start, end});
    }

    sort(intervals.begin(), intervals.end());

    string lastEnd = "00:00:00";
    for(const auto &interval : intervals) {
        if(interval.first != lastEnd) {
            cout << lastEnd << " - " << interval.first << endl;
        }
        lastEnd = interval.second;
    }

    if(lastEnd != "23:59:59") {
        cout << lastEnd << " - " << "23:59:59" << endl;
    }

    return 0;
}
//屎山版本
#include <bits/stdc++.h>
using namespace std;

struct T { 
    int h, m, s; 
    bool operator<(const T& other) const {
        if (h != other.h) return h < other.h;
        if (m != other.m) return m < other.m;
        return s < other.s;
    }
};

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n; cin >> n;
    vector<pair<T, T>> v(n);

    // 快速输入
    auto read = [](T& t) {
        char _;
        cin >> t.h >> _ >> t.m >> _ >> t.s;
    };

    for (auto& [s, e] : v) {
        read(s);
        string _; cin >> _;  // 跳过" - "
        read(e);
    }

    // 自定义排序
    sort(v.begin(), v.end(), [](auto& a, auto& b) {
        return a.first < b.first;
    });

    // 检查空缺
    T last{0, 0, 0};
    for (auto& [s, e] : v) {
        if (last < s) {
            // 统一用 printf 保证格式
            printf("%02d:%02d:%02d - %02d:%02d:%02d\n", 
                last.h, last.m, last.s,
                s.h, s.m, s.s
            );
        }
        if (e < last) {
            // 处理重叠情况，题目保证没有重叠，所以可以忽略
        } else {
            last = e;
        }
    }

    // 检查最后时间段
    T end{23, 59, 59};
    if (last < end) {
        printf("%02d:%02d:%02d - 23:59:59\n", 
            last.h, last.m, last.s
        );
    }
}

拓扑角度下的排序

#include<bits/stdc++.h>
using namespace std;

const int N = 100010;

unordered_map<string,int> d;
unordered_map<string,vector<string>> g;

vector<string> get(string str)
{
    vector<string> res;
    string word;
    for(auto &c:str)
    {
        if(c=='.')
        {
            res.push_back(word);
            if(!d.count(word)) d[word]=0;
            word="";
        }
        else word+=c;
    }
    res.push_back(word);
    if(!d.count(word)) d[word]=0;
    return res;
}

vector<string> topsort()
{
    priority_queue<string,vector<string>,greater<string>> Q;
    for(auto &[k,v]:d) 
        if(!v)
            Q.push(k);

    vector<string> res;
    while(!Q.empty())
    {
        string t=Q.top();Q.pop();
        res.push_back(t);
        for(auto &p:g[t])
            if(--d[p]==0)
                Q.push(p);
    }
    return res;
}

int main()
{
    ios::sync_with_stdio(false);

    int n;cin>>n;
    string str;cin>>str;
    vector<string> last=get(str);

    for(int i=0;i<n-1;i++)
    {
        cin>>str;
        vector<string> cur=get(str);
        if(last.size()==cur.size())
        {
            for(int j=0;j<(int)cur.size();j++)
                if(last[j]!=cur[j])
                {
                    g[last[j]].push_back(cur[j]);
                    d[cur[j]]++;
                    break;
                }
        }
        last=cur;
    }

    vector<string> res=topsort();
    cout<<res[0];
    for(int i=1;i<(int)res.size();i++)
        cout<<"."<<res[i];
    return 0;
} 

牛逼的双向dijk以及优先队列（muiltset）维护集合

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<LL, int> PLI;
const LL INF = LLONG_MAX;

struct Edge {
    int v, w;
};

vector<vector<Edge>> h, rh;
vector<LL> a, dis1, dis2;
vector<bool> st;
int n, m, q;

void dijkstra(const vector<vector<Edge>>& graph, vector<LL>& dis, int s) {
    st.assign(n + 1, false);
    dis.assign(n + 1, INF);
    priority_queue<PLI, vector<PLI>, greater<PLI>> Q;
    Q.push({0, s});
    dis[s] = 0;

    while (!Q.empty()) {
        int t = Q.top().second;
        Q.pop();
        if (st[t]) continue;
        st[t] = true;
        for (const Edge& e : graph[t]) {
            if (dis[t] + e.w < dis[e.v]) {
                dis[e.v] = dis[t] + e.w;
                Q.push({dis[e.v], e.v});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> q;
    h.resize(n + 1);
    rh.resize(n + 1);
    a.resize(n + 1);

    while (m--) {
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        h[u].push_back({v, c});
        rh[v].push_back({u, d});
    }

    for (int i = 1; i <= n; i++) cin >> a[i];

    dijkstra(h, dis1, 1);
    dijkstra(rh, dis2, n);

    multiset<LL> S;
    for (int i = 1; i <= n; i++) {
        if (dis1[i] != INF && dis2[i] != INF) {
            S.insert(dis1[i] + (dis2[i] + a[i] - 1) / a[i]);
        }
    }

    while (q--) {
        int x, y;
        cin >> x >> y;
        if (dis1[x] != INF && dis2[x] != INF) {
            S.erase(S.find(dis1[x] + (dis2[x] + a[x] - 1) / a[x]));
            a[x] = y;
            S.insert(dis1[x] + (dis2[x] + a[x] - 1) / a[x]);
        }
        cout << *S.begin() << '\n';
    }

    return 0;
}

dfs/记忆化？

错误的遍历：导致路径苏更多
hack：
o
| \
| /
o
|
o
这种会重复计数
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m;
int st, ed;
vector<int> adj[1000];
int cnt[1000];
bool ok;
void dfs(int u) {
    if (adj[u].empty()&&u != ed) {
       ok=true;
    }
    for (int son : adj[u]) {
        cnt[son] += cnt[u];
        dfs(son);

    }
}

signed main() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int s1, s2;
        cin >> s1 >> s2;
        adj[s1].push_back(s2);
    }
    cin >> st >> ed;

    cnt[st] = 1;
    dfs(st);
    cout << cnt[ed] << " ";
    if (ok) {
        cout << "No";
    } else {
        cout << "Yes";
    }
    return 0;
}
//正确代码：记忆化搜索
#include <bits/stdc++.h>
using namespace std;
#define FAST ios::sync_with_stdio(false);cin.tie(0);
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define rrep(i,a,b) for(int i=a;i>=b;--i)
#define elif else if
#define mem(arr,val) memset(arr,val,sizeof(arr))
typedef long long ll;
typedef unsigned long long ull;

int n, m;
vector< vector<int> > fmp;  //vector实现图的邻接表
vector<int> step;
vector<bool> vis;
int u, v, a, b;
bool ok;

void dfs(int r) {
    vis[r] = true;
    if (fmp[r].size() == 0 && r != b) {
        ok = false;
    }
    for (int& i : fmp[r]) {
        if (!vis[i]) dfs(i);
        step[r] += step[i];
    }
}
int main() {
    FAST
    cin >> n >> m;
    fmp.resize(n + 1);
    step.resize(n + 1, 0);
    vis.resize(n + 1, false);
    ok = true;
    //以上为初始化
    rep(i, 1, m) {
        cin >> u >> v;
        fmp[u].push_back(v);
    }
    cin >> a >> b;
    step[b] = 1;
    vis[b] = true;
    dfs(a);     //进行搜索
    cout << step[a];
    if (ok) {
        cout << " Yes" << endl;
    } else {
        cout << " No" << endl;
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector< vector<int> > fmp;  //vector实现图的邻接表
vector<int> step;
vector<bool> vis;
int u, v, a, b;
bool ok;

void dfs(int r) {
    vis[r] = true;
    if (fmp[r].size() == 0 && r != b) {
        ok = false;
    }
    for (int& i : fmp[r]) {
        if (!vis[i]) dfs(i);
        step[r] += step[i];
    }
}

int main() {
    cin >> n >> m;
    fmp.resize(n + 1);
    step.resize(n + 1, 0);
    vis.resize(n + 1, false);
    ok = true;
    //以上为初始化
    for (int i = 1; i <= m; i++) {
        cin >> u >> v;
        fmp[u].push_back(v);
    }
    cin >> a >> b;
    step[b] = 1;
    vis[b] = true;
    dfs(a);     //进行搜索
    cout << step[a];
    if (ok) {
        cout << " Yes" << endl;
    } else {
        cout << " No" << endl;
    }
    return 0;
}

暴力偏分技巧

子树逆序数

//采用权值线段树插入法，或者树状数组
//fact:dfs序就是每个节点子节点数全排列的乘法
//s1表示以及确定父子关系的逆序数：就是cnt*fact
：
对于每个节点 u，统计其所有祖先中编号比 u 大的节点数量，并累加得到总和
//s2表示不确定的，取决于美剧顺序
：
在回溯到节点 u 时，统计剩余未访问节点中不属于 u 的子树的节点数。
ans:
​​固定部分​​：s1⋅fact，表示所有DFS序中必然存在的逆序对总和。
​​可变部分​​：s2⋅fact*(1/4)
 ，表示跨子树节点对的期望逆序对总和。
（1）树状数组版本
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 3e5 + 10, MOD = 1e9+7;

vector<int> g[N];
int sz[N], tr[N];
int n, root;
LL fact = 1, s1, s2;

inline int lowbit(int x) { return x & -x; }
void add(int x, int v) {
    for (; x <= n; x += lowbit(x)) tr[x] += v;
}
int sum(int x) {
    int res = 0;
    for (; x > 0; x -= lowbit(x)) res += tr[x];
    return res;
}

void dfs(int u, int fa) {
    add(u, 1);
    s1 = (s1 + sum(n) - sum(u)) % MOD;

    sz[u] = 1;
    int cnt = 0;
    for (int v : g[u]) {
        if (v == fa) continue;
        dfs(v, u);
        sz[u] += sz[v];
        cnt++;
    }

    for (int i = 1; i <= cnt; i++) fact = fact * i % MOD;

    int rem = (n - (sum(n) + sz[u] - 1) + MOD) % MOD; // sum(n)为已访问个数
    s2 = (s2 + rem) % MOD;

    add(u, -1);
}

int main() {
    scanf("%d%d", &n, &root);
    for (int i = 0; i < n - 1; i++) {
        int u, v; scanf("%d%d", &u, &v);
        g[u].push_back(v); g[v].push_back(u);
    }
    dfs(root, -1);
    LL ans = (s1 * fact % MOD + s2 * fact % MOD * 250000002 % MOD) % MOD;
    printf("%lld\n", ans);
    return 0;
}
（2）线段树版本
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 3e5 + 10, MOD = 1e9+7;

vector<int> g[N];
int sz[N], n, root;
LL fact = 1, s1, s2;

// 递归线段树实现
int tree[4 * N];
void update(int u, int l, int r, int pos, int val) {
    if (l == r) { tree[u] += val; return; }
    int mid = (l + r) >> 1;
    if (pos <= mid) update(u<<1, l, mid, pos, val);
    else update(u<<1|1, mid+1, r, pos, val);
    tree[u] = tree[u<<1] + tree[u<<1|1];
}

int query(int u, int l, int r, int L, int R) {
    if (r < L || R < l) return 0;
    if (L <= l && r <= R) return tree[u];
    int mid = (l + r) >> 1;
    return query(u<<1, l, mid, L, R) + query(u<<1|1, mid+1, r, L, R);
}

void dfs(int u, int fa) {
    // 插入当前节点
    update(1, 1, n, u, 1);
    s1 = (s1 + query(1, 1, n, u + 1, n)) % MOD;

    sz[u] = 1;
    int cnt = 0;
    for (int v : g[u]) {
        if (v == fa) continue;
        dfs(v, u);
        sz[u] += sz[v];
        cnt++;
    }

    // 累积子节点排列数
    for (int i = 1; i <= cnt; i++) fact = fact * i % MOD;

    // 计算贡献 remaining - sz[u] + 1
    int vis = query(1, 1, n, 1, n);
    int rem = (n - vis - sz[u] + 1 + MOD) % MOD;
    s2 = (s2 + rem) % MOD;

    // 回溯时移除当前节点
    update(1, 1, n, u, -1);
}

int main() {
    scanf("%d%d", &n, &root);
    for (int i = 0; i < n - 1; i++) {
        int u, v; scanf("%d%d", &u, &v);
        g[u].push_back(v); g[v].push_back(u);
    }
    dfs(root, -1);
    LL ans = (s1 * fact % MOD + s2 * fact % MOD * 250000002 % MOD) % MOD; // inv4=250000002
    printf("%lld\n", ans);
    return 0;
}