思路 当我们可以将 对 看作 条双向边之后，能交换位置的点可以看作是联通的，因此我们会得到若干个连通块，由于 对 的使用次数与顺序不受限制，因此在每一个连通块中可以通过若干次交换不同位置上的值，使得该连通块中的数值从小到大排序，即为该连通块所能得到的最小字典序，将每一个连通块都在块内排序之后，即为最终答案。时间复杂度： 题解 /** * struct Point { * int x; * int y; * }; */ class Solution { #define maxn 100010 private: vector<int> g[maxn]; vector<int&gt...

思路 牛牛希望走的距离尽可能短，牛妹希望牛牛走的距离尽可能长，因此，牛妹会放到一个点 , 该点要满足与牛妹起点 的距离小于该点与牛牛起点的距离，通过 dfs 分别求出 号点和 号点到其他点的距离，对满足条件的点中，取一个与 号点距离的最大值即可。时间复杂度： /** * struct Point { * int x; * int y; * }; */ class Solution { private: #define maxn 100010 vector<int> g[maxn]; int dis[2][maxn]; public: void dfs(int x, int fa, ...

思路 统计从结点 到叶子节点路径权值和小于等于 的叶子数量即可。时间复杂度： Code /** * struct Point { * int x; * int y; * }; */ class Solution { private: #define maxn 100010 vector<int> g[maxn]; int val[maxn]; int ans; public: /** * 从 1 到 n 每个结点的权值。 * @param n int整型 * @param Edge Point类vector (u, v) 集合 * @param q int整型 * @param Q...

思路 可将数轴上求前缀和的思路变换一下，转成在有根树上从根结点向叶结点求树上前缀和。时间复杂度  Code /** * struct Point { * int x; * int y; * }; */ class Solution { private: #define maxn 100010 vector<int> g[maxn]; vector<long> val; public: /** * 从 1 到 n 每个结点的权值。 * @param n int整型 * @param Edge Point类vector (u, v) 集合 * @param q int整型 ...

思路 将所有的字符串插到字典树中，将串的结束点权值加一。再次遍历所有字符串，统计其在字典树路径上的权值和。 Code class Solution { #define maxn 2200010 private: int trie[maxn][26], pn = 0; int ed[maxn]; public: /** * 返回新集合的种类数 * @param n int整型 集合大小 * @param m int整型 限制数量 * @param limit Point类vector 不能同时出现的(u,v)集合 * @return int整型 */ void insert(string s) ...

思路 由于 只有 ，因此我们可以暴力枚举当前数是否被选即可。 时间复杂度  class Solution { private: int mp[21][21]; int vis[21]; int ans; public: /** * 返回新集合的种类数 * @param n int整型 集合大小 * @param m int整型 限制数量 * @param limit Point类vector 不能同时出现的(u,v)集合 * @return int整型 */ void dfs(int x, int n) { if (x == n + 1) { ++ans; return; } dfs(x + ...

思路 易知： 前序遍历顺序为：根、左子树、右子树；中序遍历顺序为：左子树、根、右子树；后序遍历顺序为：左子树、右子树、根； 由前序遍历可知，整棵树的根节点是 。 对于样例：  3 2 1 4 51 5 4 2 3  结合前序、后序遍历可得整棵树的结构：   得到规律： 在先序遍历序列中，根节点之后是左儿子结点；在后序遍历序列中，根节点之前是右儿子结点。 枚举先序遍历中的节点，结合其在后序遍历中的位置，判断其子树所包含节点范围，递归求解即可。 Code class Solution{ private: vector<int> ans; vector<int> pre, s...

思路 从 号点对边dfs，判断 号点是否在一个环中即可。时间复杂度： code class Solution { #define maxn 100010 private: int n, m, L; vector<int> g[maxn]; bool vis[maxn]; bool fg = false; public: void dfs(int x, int fa = 0) { if (fg) return; if (fa && x == 1) return fg=1,void(); if (vis[x]) return; vis[x] = 1; for (auto...

思路 最起初显然可以得到一个时间复杂度为 O(n2)O(n^2)O(n2) 的暴力做法，思考一下只会会发现两条性质：   当我们固定某个结点为根节点时，对于结点 xxx，设 dis[x]dis[x]dis[x] 为结点 xxx 与其子树中所有结点的距离和，sz[x]sz[x]sz[x] 为其子树的大小，则易得：dis[x]=∑v(dis[v]+sz[v])dis[x] = \sum_{v}(dis[v]+sz[v])dis[x]=∑v​(dis[v]+sz[v])。   设 f[x]f[x]f[x] 为结点 xxx 的权值，若 xxx 为 vvv 的父节点，则有关系 f[v]=dis[v]+(...

思路 假设总共 个城市构成了一棵树，任意一条边，都会将城市分成两部分，假设左边有 个，则右边有 个，那么左侧的每个城市和右侧的每个城市都会相连，即经过该边 次，一旦被破坏，造成的损失是 ，只需在dfs过程中取一下每条边贡献的最大值即可，时间复杂度 。 如下图所示：  Code class Solution { #define ll long long #define maxn 100010 #define pii pair<int, int> private: int n; int sz[maxn]; // sz[x] 表示结点 x 的子树结点数量 ll ans; vector&l...

思路 朴素做法 对每个节点做一次dfs，求出其到其他节点的距离，期间保留最大值即可。 时间复杂度  该做法可通过 的数据 Code class Solution { #define pii pair<int, int> #define ll long private: ll ans; vector<pii> g[100010]; public: void dfs(int x, int fa, int sum = 0) { for (auto cur: g[x]) { int v = cur.first, w = cur.second; if (v == fa) cont...