树的重心、直径、DFS序与欧拉序

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

const int MAXN = 50005;
int n, siz[MAXN], f[MAXN];
vector<int> g[MAXN];

void dfs1(int u, int fa) {          // 求子树大小
    siz[u] = 1;
    for (int v : g[u]) {
        if (v == fa) continue;
        dfs1(v, u);
        siz[u] += siz[v];
    }
}

void dfs2(int u, int fa) {          // 换根计算最大块
    f[u] = n - siz[u];                    // 父亲那一侧
    for (int v : g[u]) {
        if (v == fa) continue;
        dfs2(v, u);
        f[u] = max(f[u], siz[v]);         // 每个儿子那一侧
    }
}

int depSum = 0;
void dfs3(int u, int fa, int d) {     // 求距离和
    depSum += d;
    for (int v : g[u]) if (v != fa) dfs3(v, u, d + 1);
}

int main() {
    ios::sync_with_stdio(0);
    cin >> n;
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        g[u].push_back(v); g[v].push_back(u);
    }
    dfs1(1, 0);
    dfs2(1, 0);

    int best = 1;
    for (int i = 2; i <= n; i++)
        if (f[i] < f[best]) best = i;     // 严格小于 → 保留编号最小的最优解

    dfs3(best, 0, 0);
    cout << best << " " << depSum << "\n";
    return 0;
}

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

const int MAXN = 50005;
struct Edge { int to, w, nxt; } e[MAXN << 1];
int n, tot, head[MAXN];
void add(int u, int v, int w) { e[++tot] = {v, w, head[u]}; head[u] = tot; }

long long dist[MAXN];

// 从 s 出发，用显式栈做 DFS 求所有点的距离，返回距离最远的点编号
int dfs(int s) {
    for (int i = 1; i <= n; i++) dist[i] = -1;   // -1 表示未访问
    stack<int> st;
    st.push(s); dist[s] = 0;
    int far = s;
    while (!st.empty()) {
        int u = st.top(); st.pop();
        if (dist[u] > dist[far]) far = u;
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].to;
            if (dist[v] == -1) {
                dist[v] = dist[u] + e[i].w;
                st.push(v);
            }
        }
    }
    return far;
}

int main() {
    ios::sync_with_stdio(0);
    cin >> n;
    for (int i = 1, u, v, w; i < n; i++) {
        cin >> u >> v >> w;
        add(u, v, w); add(v, u, w);
    }
    int A = dfs(1);        // 第一遍：从任意点找最远点 A
    int B = dfs(A);        // 第二遍：从 A 找最远点 B
    cout << A << " " << B << " " << dist[B] << "\n";
    return 0;
}

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

const int MAXN = 200005;
int n, m, a[MAXN], tin[MAXN], tout[MAXN], timer;
long long bit[MAXN];
vector<int> g[MAXN];

void dfs(int u, int fa) {
    tin[u] = ++timer;                     // 进入时间戳
    for (int v : g[u]) if (v != fa) dfs(v, u);
    tout[u] = timer;                      // 离开时记的是最后一个子孙的时间戳
}

void update(int i, long long v) {          // 树状数组单点加
    for (; i <= n; i += i & -i) bit[i] += v;
}
long long query(int i) {                   // 前缀和
    long long s = 0;
    for (; i > 0; i -= i & -i) s += bit[i];
    return s;
}

int main() {
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        g[u].push_back(v); g[v].push_back(u);
    }
    dfs(1, 0);
    for (int i = 1; i <= n; i++) update(tin[i], a[i]);  // 按 DFS 序建树状数组

    while (m--) {
        int op, u; long long x;
        cin >> op >> u;
        if (op == 1) {
            cin >> x;
            update(tin[u], x);                                  // 单点修改
        } else {
            cout << query(tout[u]) - query(tin[u] - 1) << "\n";  // 区间查询
        }
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50005;
int n, siz[MAXN], d1[MAXN];
long long sum[MAXN];
vector<int> g[MAXN];

void dfs1(int u, int fa, int d) {
    siz[u] = 1; d1[u] = d;
    for (int v : g[u]) {
        if (v == fa) continue;
        dfs1(v, u, d + 1);
        siz[u] += siz[v];
    }
}
void dfs2(int u, int fa) {         // 换根转移
    for (int v : g[u]) {
        if (v == fa) continue;
        sum[v] = sum[u] + (n - 2 * siz[v]);   // 核心公式
        dfs2(v, u);
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin >> n;
    for (int i = 1, u, v; i < n; i++) { cin >> u >> v; g[u].push_back(v); g[v].push_back(u); }
    dfs1(1, 0, 0);
    for (int i = 1; i <= n; i++) sum[1] += d1[i];
    dfs2(1, 0);
    int best = 1;
    for (int i = 2; i <= n; i++) if (sum[i] < sum[best]) best = i;
    cout << best << " " << sum[best] << "\n";
    return 0;
}

// ① 两次 DFS 取直径，记录直径上的点序列 path[] 和前缀和 pre[]
int A = dfs(1);  int B = dfs(A);
// 从 B 回溯到 A 得到 path（用父亲数组 fa 还原）

// ② 求每个直径点到「非直径分支」的最大距离 f[i]
for (int i = 1; i <= k; i++) {
    onPath[path[i]] = 1;
}
for (int i = 1; i <= k; i++)
    f[i] = maxDep(path[i], 0);   // 不经过其他直径点向下走的最大深度

// ③ 双指针 + 单调队列求窗口内 f 的最大值
int ans = INT_MAX;
deque<int> q;                       // 存下标，f 值单调递减
for (int l = 1, r = 0; l <= k; l++) {
    while (r + 1 <= k && pre[r + 1] - pre[l] <= s) {
        ++r;
        while (!q.empty() && f[q.back()] <= f[r]) q.pop_back();
        q.push_back(r);
    }
    while (!q.empty() && q.front() < l) q.pop_front();
    int cur = max({f[q.front()], pre[l], pre[k] - pre[r]});
    ans = min(ans, cur);
}
cout << ans << "\n";

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int n, m, tin[MAXN], tout[MAXN], timer;
long long a[MAXN], bit[MAXN];
vector<int> g[MAXN];

void dfs(int u, int fa) {
    tin[u] = ++timer;
    for (int v : g[u]) if (v != fa) dfs(v, u);
    tout[u] = timer;
}
void update(int i, long long v) { for (; i <= n; i += i & -i) bit[i] += v; }
long long query(int i) { long long s = 0; for (; i; i -= i & -i) s += bit[i]; return s; }

int main() {
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1, u, v; i < n; i++) { cin >> u >> v; g[u].push_back(v); g[v].push_back(u); }
    dfs(1, 0);
    for (int i = 1; i <= n; i++) update(tin[i], a[i]);
    while (m--) {
        int op, u; cin >> op >> u;
        if (op == 1) { long long x; cin >> x; update(tin[u], x); }
        else cout << query(tout[u]) - query(tin[u] - 1) << "\n";
    }
    return 0;
}

int n, siz[MAXN], tin[MAXN], tout[MAXN], timer, cen, d1[MAXN], d2[MAXN];
int bestMax = INT_MAX;   // 重心的最大子树值
int diam = 0;             // 直径长度
vector<int> g[MAXN];

void dfs(int u, int fa) {
    tin[u] = ++timer;
    siz[u] = 1;
    d1[u] = d2[u] = 0;
    int mx = 0;                        // u 的最大子树（不含上方）
    for (int v : g[u]) {
        if (v == fa) continue;
        dfs(v, u);
        siz[u] += siz[v];
        mx = max(mx, siz[v]);

        // 直径：维护最长链与次长链
        int len = d1[v] + 1;             // 无权树；带权则用 e[i].w
        if (len > d1[u]) { d2[u] = d1[u]; d1[u] = len; }
        else if (len > d2[u]) d2[u] = len;
    }
    diam = max(diam, d1[u] + d2[u]);      // 经过 u 的最长路径

    // 重心：加入「上方那一块」再比较
    int cur = max(mx, n - siz[u]);
    if (cur < bestMax) { bestMax = cur; cen = u; }
    tout[u] = timer;
}