5 条题解

  • 0
    @ 2026-10-13 19:30:37

    满分解法（100 分）

    把合法性拆成两个条件

    任意点集在树上的诱导子图不会出现环，因此一定是森林。一个非空森林是一条简单路径，当且仅当：

    1. 它只有一个连通块；
    2. 每个点在诱导子图中的度数都不超过 22。

    条件 1 排除了若干条互不相连的路径，条件 2 排除了分叉。下面从左到右枚举片段右端点 rr，分别维护这两个条件，再统计同时满足它们的左端点。

    用双指针维护度数限制

    固定右端点 rr。如果 [l,r][l,r] 中所有点的诱导度数都不超过 22，那么删去最左边的点后只会删除诱导边，剩余点的度数不会增加，所以 [l+1,r][l+1,r] 仍满足限制。

    因此，对当前 rr，满足度数限制的左端点一定构成一个后缀

    L,L+1,…,r.L,L+1,\ldots,r.

    维护窗口 [L,r][L,r]，记录每个点是否在窗口中、它当前的诱导度数，以及度数至少为 33 的点数 badbad。

    加入新点 u=pru=p_r 时，枚举 uu 的邻点。每遇到一个已经在窗口中的邻点 vv，诱导子图新增边 (u,v)(u,v)，于是 u,vu,v 的度数各加 11。若某个点从合法度数变为至少 33，就相应更新 badbad。

    只要 bad>0bad>0，当前窗口就不满足度数限制。此时移出 x=pLx=p_L：枚举仍在窗口内的邻点，删除这些诱导边并把两端度数各减 11，再令 LL 加 11。当 bad=0bad=0 时，窗口 [L,r][L,r] 满足限制；由前面的单调性，所有更靠右的左端点也满足，而任何更靠左的左端点都在移动过程中被证实不满足，所以此时的 LL 恰是最小合法左端点。

    每个点只加入窗口一次、移出窗口至多一次。加入和移出时各扫描一次该点的邻接表，而树的邻接表长度总和为 2(n−1)2(n-1)，所以这一部分总计 O(n)O(n)。

    用点数减边数表示连通块数

    对固定的 rr 和每个 1≤l≤r1\le l\le r，记诱导子图的边数为 ElE_l，定义

    fl=(r−l+1)−El.f_l=(r-l+1)-E_l.

    森林中一个含 vv 个点的连通块恰有 v−1v-1 条边。若把所有连通块分别应用这个关系并求和，就得到

    连通块数=点数−边数.\text{连通块数}=\text{点数}-\text{边数}.

    所以 flf_l 正是片段 [l,r][l,r] 的诱导子图连通块数。片段非空，故始终有 fl≥1f_l\ge 1；它连通当且仅当 fl=1f_l=1。

    右端点增加时的区间修改

    假设已经处理完位置 r−1r-1，现在加入 u=pru=p_r。

    首先，新点会出现在所有 l≤rl\le r 的片段中，因此这些片段的点数都增加 11：

    f1,f2,…,fr全部加 1.f_1,f_2,\ldots,f_r\quad\text{全部加 }1.

    再考虑 uu 的一个已经出现的邻点 v=pxv=p_x，其中 x<rx<r。边 (u,v)(u,v) 属于片段 [l,r][l,r]，当且仅当该片段同时包含位置 xx，也就是 l≤xl\le x。因此这条新增诱导边让

    f1,f2,…,fx全部减 1.f_1,f_2,\ldots,f_x\quad\text{全部减 }1.

    对 uu 的每个已出现邻点各做一次这样的前缀减法，就准确加入了所有以 uu 为新端点的诱导边。每条树边只会在它两个端点中较晚出现的那个端点加入时处理一次。

    以样例中 r=4r=4、pr=4p_r=4 为例。先对 [1,4][1,4] 加 11；点 44 的已出现邻点是位置 22 的点 11，所以再对 [1,2][1,2] 减 11。尚未出现的点 55 不会产生修改。这正好对应：只有左端点不超过 22 的片段已经同时包含边 (1,4)(1,4) 的两个端点。

    线段树统计答案

    线段树按左端点 l=1,2,…,nl=1,2,\ldots,n 建立，每个节点维护：

    • 区间内 flf_l 的最小值；
    • 这个最小值出现的次数；
    • 区间加的懒标记。

    初始还没有加入右端点，所有位置置为 00。处理右端点 rr 时按上一节完成一次 [1,r][1,r] 加一和若干次前缀减一；只查询已经有含义的范围 [L,r][L,r]。

    这一范围中的每个左端点都已经满足度数限制。另一方面，其中的 flf_l 都是非空森林的连通块数，不可能小于 11。所以：

    • 若区间最小值大于 11，没有连通片段；
    • 若区间最小值等于 11，最小值出现次数就是连通片段数，也就是当前 rr 对答案的贡献。

    把所有右端点的贡献相加即可。答案最多为 n(n+1)/2n(n+1)/2，需要使用 64 位整数。

    正确性说明

    双指针始终把 LL 维护为使 [L,r][L,r] 最大诱导度数不超过 22 的最小左端点，因此查询范围 [L,r][L,r] 恰好包含所有满足度数限制的候选。

    线段树的初始值和每次修改分别精确计入当前片段的每个点和每条诱导边，所以它在位置 ll 维护的值始终等于 [l,r][l,r] 诱导森林的点数减边数，也就是连通块数。查询中值为 11 的位置恰好对应连通片段。

    因此被计数的片段同时连通且最大诱导度数不超过 22，必为简单路径；任意合法片段的左端点也同时落入度数后缀且在线段树中取值 11，不会漏计。

    复杂度

    每个点至多加入和移出双指针窗口各一次，度数维护共 O(n)O(n)。每个右端点有一次区间加，每条边产生一次前缀减，另有一次区间查询，共 O(n)O(n) 次线段树操作。

    总时间复杂度为 O(nlog⁡n)O(n\log n)，空间复杂度为 O(n)O(n)。

    AC 代码（C++20）

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

struct SegTree {
  int n;
  vector<int> mn, cnt, tag;

  explicit SegTree(int n) : n(n), mn(4 * n), cnt(4 * n), tag(4 * n) {
    build(1, 1, n);
  }

  void build(int u, int l, int r) {
    if (l == r) {
      cnt[u] = 1;
      return;
    }
    int mid = (l + r) / 2;
    build(2 * u, l, mid);
    build(2 * u + 1, mid + 1, r);
    pull(u);
  }

  void pull(int u) {
    mn[u] = min(mn[2 * u], mn[2 * u + 1]);
    cnt[u] = 0;
    if (mn[2 * u] == mn[u]) cnt[u] += cnt[2 * u];
    if (mn[2 * u + 1] == mn[u]) cnt[u] += cnt[2 * u + 1];
  }

  void apply(int u, int value) {
    mn[u] += value;
    tag[u] += value;
  }

  void push(int u) {
    if (tag[u] == 0) return;
    apply(2 * u, tag[u]);
    apply(2 * u + 1, tag[u]);
    tag[u] = 0;
  }

  void add(int ql, int qr, int value) {
    add(1, 1, n, ql, qr, value);
  }

  void add(int u, int l, int r, int ql, int qr, int value) {
    if (ql <= l && r <= qr) {
      apply(u, value);
      return;
    }
    push(u);
    int mid = (l + r) / 2;
    if (ql <= mid) add(2 * u, l, mid, ql, qr, value);
    if (mid < qr) add(2 * u + 1, mid + 1, r, ql, qr, value);
    pull(u);
  }

  pair<int, int> query(int ql, int qr) {
    return query(1, 1, n, ql, qr);
  }

  pair<int, int> query(int u, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return {mn[u], cnt[u]};
    push(u);
    int mid = (l + r) / 2;
    pair<int, int> res = {INT_MAX, 0};
    auto merge = [&](pair<int, int> part) {
      if (part.first < res.first) res = part;
      else if (part.first == res.first) res.second += part.second;
    };
    if (ql <= mid) merge(query(2 * u, l, mid, ql, qr));
    if (mid < qr) merge(query(2 * u + 1, mid + 1, r, ql, qr));
    return res;
  }
};

void solve() {
  int n;
  cin >> n;
  vector<vector<int>> adj(n + 1);
  for (int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  vector<int> p(n + 1), pos(n + 1);
  for (int i = 1; i <= n; ++i) {
    cin >> p[i];
    pos[p[i]] = i;
  }

  SegTree seg(n);
  vector<int> deg(n + 1);
  vector<char> active(n + 1);
  int left = 1, bad = 0;
  i64 ans = 0;

  auto change_degree = [&](int u, int delta) {
    if (deg[u] >= 3) --bad;
    deg[u] += delta;
    if (deg[u] >= 3) ++bad;
  };

  for (int r = 1; r <= n; ++r) {
    int u = p[r];
    seg.add(1, r, 1);
    for (int v : adj[u]) {
      if (pos[v] < r) seg.add(1, pos[v], -1);
      if (active[v]) {
        change_degree(u, 1);
        change_degree(v, 1);
      }
    }
    active[u] = 1;

    while (bad > 0) {
      int x = p[left++];
      for (int v : adj[x]) {
        if (!active[v]) continue;
        change_degree(x, -1);
        change_degree(v, -1);
      }
      active[x] = 0;
    }

    auto [minimum, count] = seg.query(left, r);
    if (minimum == 1) ans += count;
  }
  cout << ans << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}
    • 0
      @ 2026-10-13 19:30:37

      三度点的四位置阈值（通过子任务 8–16，共 45 分）

      先按“点数减边数”维护连通性。对固定右端点 rr 和左端点 ll，令

      fl=(r−l+1)−El,f_l=(r-l+1)-E_l,

      其中 ElE_l 是片段诱导边数。诱导子图是森林，所以 flf_l 是连通块数。加入 prp_r 时对 [1,r][1,r] 加 11；若它有一个已出现邻点位于位置 xx，再对 [1,x][1,x] 减 11。用支持区间加、区间最小值和最小值计数的线段树维护这些值。

      还需限制诱导度数不超过 22。本档中一个点的原树度数最多为 33。度数小于 33 的点永远不会违规；对一个三度点 uu，只有当片段同时包含 uu 和它的三个邻点时，uu 的诱导度数才会达到 33。

      取这四个点在排列中的位置，设最小值为 aa、最大值为 bb。片段 [l,r][l,r] 同时包含四个位置，当且仅当

      l≤a且r≥b.l\le a\quad\text{且}\quad r\ge b.

      所以从右端点到达 bb 开始，必须要求 l≥a+1l\ge a+1 才能避开这个三度点。预处理所有三度点，在位置 bb 记录限制 a+1a+1；枚举右端点时维护这些限制的前缀最大值 LL。这样 [L,r][L,r] 恰好是满足所有度数限制的左端点范围。

      每个右端点完成连通块数的区间修改后，只查询线段树的 [L,r][L,r]。其中最小值若为 11，最小值出现次数就是同时连通且无三度分叉的片段数。

      预处理每个三度点共 O(n)O(n)，线段树部分为 O(nlog⁡n)O(n\log n)；总空间复杂度为 O(n)O(n)。

      参考代码（C++20）

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

struct SegTree {
  int n;
  vector<int> mn, cnt, tag;

  explicit SegTree(int n) : n(n), mn(4 * n), cnt(4 * n), tag(4 * n) {
    build(1, 1, n);
  }

  void build(int u, int l, int r) {
    if (l == r) {
      cnt[u] = 1;
      return;
    }
    int mid = (l + r) / 2;
    build(2 * u, l, mid);
    build(2 * u + 1, mid + 1, r);
    pull(u);
  }

  void pull(int u) {
    mn[u] = min(mn[2 * u], mn[2 * u + 1]);
    cnt[u] = 0;
    if (mn[2 * u] == mn[u]) cnt[u] += cnt[2 * u];
    if (mn[2 * u + 1] == mn[u]) cnt[u] += cnt[2 * u + 1];
  }

  void apply(int u, int value) {
    mn[u] += value;
    tag[u] += value;
  }

  void push(int u) {
    if (tag[u] == 0) return;
    apply(2 * u, tag[u]);
    apply(2 * u + 1, tag[u]);
    tag[u] = 0;
  }

  void add(int ql, int qr, int value) {
    add(1, 1, n, ql, qr, value);
  }

  void add(int u, int l, int r, int ql, int qr, int value) {
    if (ql <= l && r <= qr) {
      apply(u, value);
      return;
    }
    push(u);
    int mid = (l + r) / 2;
    if (ql <= mid) add(2 * u, l, mid, ql, qr, value);
    if (mid < qr) add(2 * u + 1, mid + 1, r, ql, qr, value);
    pull(u);
  }

  pair<int, int> query(int ql, int qr) {
    return query(1, 1, n, ql, qr);
  }

  pair<int, int> query(int u, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return {mn[u], cnt[u]};
    push(u);
    int mid = (l + r) / 2;
    pair<int, int> res = {INT_MAX, 0};
    auto merge = [&](pair<int, int> part) {
      if (part.first < res.first) res = part;
      else if (part.first == res.first) res.second += part.second;
    };
    if (ql <= mid) merge(query(2 * u, l, mid, ql, qr));
    if (mid < qr) merge(query(2 * u + 1, mid + 1, r, ql, qr));
    return res;
  }
};

void solve() {
  int n;
  cin >> n;
  vector<vector<int>> adj(n + 1);
  for (int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  vector<int> p(n + 1), pos(n + 1);
  for (int i = 1; i <= n; ++i) {
    cin >> p[i];
    pos[p[i]] = i;
  }

  vector<int> trigger(n + 1);
  for (int u = 1; u <= n; ++u) {
    if ((int)adj[u].size() != 3) continue;
    int first = pos[u], last = pos[u];
    for (int v : adj[u]) {
      first = min(first, pos[v]);
      last = max(last, pos[v]);
    }
    trigger[last] = max(trigger[last], first + 1);
  }

  SegTree seg(n);
  int left = 1;
  i64 ans = 0;
  for (int r = 1; r <= n; ++r) {
    left = max(left, trigger[r]);
    int u = p[r];
    seg.add(1, r, 1);
    for (int v : adj[u]) {
      if (pos[v] < r) seg.add(1, pos[v], -1);
    }
    auto [minimum, count] = seg.query(left, r);
    if (minimum == 1) ans += count;
  }
  cout << ans << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}
      • 0
        @ 2026-10-13 19:30:36

        最大度数为 2 时只维护连通性（通过子任务 8–12，共 25 分）

        树中每个点的度数都不超过 22，所以任意诱导子图的点度数也不超过 22。度数条件自动满足，只需统计连通片段。

        固定右端点 rr。对每个 1≤l≤r1\le l\le r，记片段 [l,r][l,r] 的诱导边数为 ElE_l，并令

        fl=(r−l+1)−El.f_l=(r-l+1)-E_l.

        诱导子图是森林，而森林的连通块数等于点数减边数，所以 flf_l 就是连通块数。片段连通当且仅当 fl=1f_l=1。

        加入新点 u=pru=p_r 时，所有 l≤rl\le r 的片段都多一个点，先把 [1,r][1,r] 的 flf_l 加 11。若 uu 的某个邻点位于排列位置 x<rx<r，边 (u,px)(u,p_x) 会且只会出现在 l≤xl\le x 的片段中，因此把前缀 [1,x][1,x] 的 flf_l 减 11。

        用线段树维护区间最小值、最小值出现次数和区间加标记。完成当前右端点的所有修改后查询 [1,r][1,r]。所有 fl≥1f_l\ge1，所以若最小值为 11，其出现次数就是当前新增的连通片段数。

        每个点产生一次区间加，每条边产生一次前缀减，每个右端点再查询一次。总时间复杂度为 O(nlog⁡n)O(n\log n)，空间复杂度为 O(n)O(n)。

        参考代码（C++20）

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

struct SegTree {
  int n;
  vector<int> mn, cnt, tag;

  explicit SegTree(int n) : n(n), mn(4 * n), cnt(4 * n), tag(4 * n) {
    build(1, 1, n);
  }

  void build(int u, int l, int r) {
    if (l == r) {
      cnt[u] = 1;
      return;
    }
    int mid = (l + r) / 2;
    build(2 * u, l, mid);
    build(2 * u + 1, mid + 1, r);
    pull(u);
  }

  void pull(int u) {
    mn[u] = min(mn[2 * u], mn[2 * u + 1]);
    cnt[u] = 0;
    if (mn[2 * u] == mn[u]) cnt[u] += cnt[2 * u];
    if (mn[2 * u + 1] == mn[u]) cnt[u] += cnt[2 * u + 1];
  }

  void apply(int u, int value) {
    mn[u] += value;
    tag[u] += value;
  }

  void push(int u) {
    if (tag[u] == 0) return;
    apply(2 * u, tag[u]);
    apply(2 * u + 1, tag[u]);
    tag[u] = 0;
  }

  void add(int ql, int qr, int value) {
    add(1, 1, n, ql, qr, value);
  }

  void add(int u, int l, int r, int ql, int qr, int value) {
    if (ql <= l && r <= qr) {
      apply(u, value);
      return;
    }
    push(u);
    int mid = (l + r) / 2;
    if (ql <= mid) add(2 * u, l, mid, ql, qr, value);
    if (mid < qr) add(2 * u + 1, mid + 1, r, ql, qr, value);
    pull(u);
  }

  pair<int, int> query(int ql, int qr) {
    return query(1, 1, n, ql, qr);
  }

  pair<int, int> query(int u, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return {mn[u], cnt[u]};
    push(u);
    int mid = (l + r) / 2;
    pair<int, int> res = {INT_MAX, 0};
    auto merge = [&](pair<int, int> part) {
      if (part.first < res.first) res = part;
      else if (part.first == res.first) res.second += part.second;
    };
    if (ql <= mid) merge(query(2 * u, l, mid, ql, qr));
    if (mid < qr) merge(query(2 * u + 1, mid + 1, r, ql, qr));
    return res;
  }
};

void solve() {
  int n;
  cin >> n;
  vector<vector<int>> adj(n + 1);
  for (int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  vector<int> p(n + 1), pos(n + 1);
  for (int i = 1; i <= n; ++i) {
    cin >> p[i];
    pos[p[i]] = i;
  }

  SegTree seg(n);
  i64 ans = 0;
  for (int r = 1; r <= n; ++r) {
    int u = p[r];
    seg.add(1, r, 1);
    for (int v : adj[u]) {
      if (pos[v] < r) seg.add(1, pos[v], -1);
    }
    auto [minimum, count] = seg.query(1, r);
    if (minimum == 1) ans += count;
  }
  cout << ans << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}
        • 0
          @ 2026-10-13 19:30:36

          排列顺序就是树上路径（通过子任务 8–9，共 10 分）

          限制保证树中存在所有边 (pi,pi+1)(p_i,p_{i+1})。这些边一共有 n−1n-1 条，而一棵 nn 个点的树也恰有 n−1n-1 条边，所以整棵树就是

          p1−p2−⋯−pnp_1-p_2-\cdots-p_n

          这条路径，不会再有其他边。

          任取连续片段 pl,pl+1,…,prp_l,p_{l+1},\ldots,p_r，其诱导子图恰好保留相邻位置之间的边，仍是一条路径。因此所有非空连续片段都合法，答案为

          1+2+⋯+n=n(n+1)2.1+2+\cdots+n=\frac{n(n+1)}2.

          读入输入需要 O(n)O(n) 时间和 O(1)O(1) 额外空间；答案使用 64 位整数。

          参考代码（C++20）

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

void solve() {
  int n;
  cin >> n;
  for (int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v;
  }
  for (int i = 1; i <= n; ++i) {
    int x;
    cin >> x;
  }
  cout << 1LL * n * (n + 1) / 2 << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}
          • 0
            @ 2026-10-13 19:30:36

            二次枚举所有片段（通过子任务 1–7，共 35 分）

            限制为 n≤3000n\le 3000 时，可以直接枚举所有片段，并在固定左端点后逐步加入右端点。

            固定 ll，先清空当前点集、各点诱导度数、诱导边数 EE 和度数至少为 33 的点数 badbad。右端点从 ll 向右移动；加入 u=pru=p_r 时，枚举 uu 的所有邻点。若邻点已经在当前点集中，就新增一条诱导边，并把边两端的诱导度数各加 11。某个点的度数从 22 变为 33 时，将 badbad 加 11。

            诱导子图是森林。当前片段有 r−l+1r-l+1 个点，因此它连通当且仅当

            E=(r−l+1)−1=r−l.E=(r-l+1)-1=r-l.

            再结合 bad=0bad=0，即可判断当前片段是否为简单路径。

            对一个固定的 ll，每个点只加入一次，所有加入操作扫描的邻接表总长度为 O(n)O(n)；枚举全部左端点后，时间复杂度为 O(n2)O(n^2)，空间复杂度为 O(n)O(n)。

            参考代码（C++20）

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

void solve() {
  int n;
  cin >> n;
  vector<vector<int>> adj(n + 1);
  for (int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  vector<int> p(n + 1);
  for (int i = 1; i <= n; ++i) cin >> p[i];

  i64 ans = 0;
  vector<int> deg(n + 1), present(n + 1);
  for (int l = 1; l <= n; ++l) {
    fill(deg.begin(), deg.end(), 0);
    fill(present.begin(), present.end(), 0);
    int edges = 0, bad = 0;
    for (int r = l; r <= n; ++r) {
      int u = p[r];
      present[u] = 1;
      for (int v : adj[u]) {
        if (!present[v]) continue;
        ++edges;
        if (deg[u] == 2) ++bad;
        if (deg[v] == 2) ++bad;
        ++deg[u];
        ++deg[v];
      }
      if (edges == r - l && bad == 0) ++ans;
    }
  }
  cout << ans << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}
            • 1

            路径片段计数

            信息

            ID
            2318
            时间
            2000ms
            内存
            1024MiB
            难度
            9
            标签
            (无)
            递交数
            34
            已通过
            2
            上传者
            1. 评测队列
            2. 服务状态
            3. 兼容模式
            3. Powered by Hydro v5.0.7