电压、农民、奇迹树、暴雨
来自 \(\texttt{happyguy}\) 的馈赠。
A. 电压
我们考虑选一条边作为那条两边结点相同的边。
首先考虑，如果不选奇环上的边。奇环上的边一定有两端结点颜色相同的，所以如果图中有奇环，奇环上的边一定被选择。
考虑偶环，偶环上的边一定不能被选，选了的话偶环上的边也必定有一条左右结点颜色相同。
所以，如果没有奇环，那么除了偶环之外的边都能选。
如果有奇环，那么必须要选的是奇环上边的交集，并且还要保证这条边不在偶环上。
如果只有一个奇环，要记得把非树边加上。
最后树上差分求。
#include <bits/stdc++.h>
using namespace std;
const int N = 100500;
int n,m;
struct Edge{
int next,to;
}e[N << 2];
int cnt = 1,h[N];
int root[N];
void Add(int u,int v) {
cnt ++;
e[cnt].next = h[u];
h[u] = cnt;
e[cnt].to = v;
}
bool vis[N];
int dep[N];
int sum[N][2];
int tot;// 奇环个数
int fa[N];
// 这个点上面那条边的编号
void dfs(int x) {
vis[x] = 1;
for(int i = h[x];i;i = e[i].next) {
int to = e[i].to;
if(i == fa[x] || (i ^ 1) == fa[x])
continue;// 防止走回去
if(vis[to]) {
// 非树边
if(dep[to] > dep[x])
continue;
int d = (dep[x] - dep[to]) & 1;
// 判奇偶环
sum[x][d] ++;
sum[to][d] --;
if(d == 0)
tot ++;
}
else {
fa[to] = i;
dep[to] = dep[x] + 1;
dfs(to);
sum[x][0] += sum[to][0];
sum[x][1] += sum[to][1];
}
}
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
for(int i = 1,u,v;i <= m; i++) {
cin >> u >> v;
Add(u,v);
Add(v,u);
}
for(int i = 1;i <= n; i++) {
if(!vis[i]) {
root[i] = 1;
dfs(i);
}
}
int ans = 0;
for(int i = 1;i <= n; i++)
if(sum[i][0] == tot && !sum[i][1] && !root[i])
ans ++;// 在所有奇环上
if(tot == 1)
ans ++;
cout << ans << "\n";
return 0;
}
B. 农民
C. 奇迹树
题目大意
给定一棵 \(n\) 个节点的树，要求构造出一个点权序列 \(E\)，满足以下三个条件：
- 所有 \(E_i\ge 1(1\le i\le n)\)。
- 对于任意一组 \((i,j)(1 ≤ i < j ≤ N)\)，使 \(|E_i-E_j|\geq \operatorname{dist}(i,j)\)，\(\operatorname{dist}(i,j)\) 即树上 \(i\) 和 \(j\) 两点距离。
- 使 \(E\) 中的最大值最小。
思路
首先只考虑前两个限制，设有点 \(i,j,k\) 满足
\[E_i < E_j < E_k \]因为有
\[E_k-E_i=E_k-E_j+E_j-E_i \]由于
\[E_k-E_j\geq \operatorname{dist}(k,j),E_j-E_i\geq \operatorname{dist}(i,j) \]所以有
\[E_k-E_i \geq \operatorname{dist}(k,j) + \operatorname{dist}(i,j) \]又因为
\[\operatorname{dist}(k,j) + \operatorname{dist}(i,j) \geq \operatorname{dist}(i,k) \]使得 \(E_k-E_j\) 尽可能小，得到
\[E_k-E_i=\operatorname{dist}(k,i) \]那么我们直接可以用欧拉序列进行构造，欧拉序列的长度为 \(2n - 1\)。
再考虑第三个限制条件，让 \(E\) 中的最大值最小。
考虑我们欧拉序列有重复走的部分，我们使那个重复走的链的部分最短，那么那一段我们就可以选取树的直径。
那么我们怎么保证固定我们最后走哪个点呢？如果一条边在直径上，我们就最后经过这条边，这样在到达直径的第二个端点时，能够保证其他的点都已经遍历过。
#include <bits/stdc++.h>
using namespace std;
const int N = 200500;
vector<int> e[N];
int n;
int dis[N];
int EndPoint,End;
void dfs1(int x,int fa) {
dis[x] = dis[fa] + 1;
if(dis[x] > dis[EndPoint])
EndPoint = x;
for(auto const &to : e[x]) {
if(to == fa)
continue;
dfs1(to,x);
}
}
void GetCal() {
dfs1(1,0);
End = EndPoint;
dfs1(EndPoint,0);
}
bool cal[N];
void dfs2(int x,int fa) {
if(x == End)
cal[x] = 1;
for(auto const &to : e[x]) {
if(to == fa)
continue;
dfs2(to,x);
cal[x] |= cal[to];
}
}
int ans[N],tot;
void dfs3(int x,int fa) {
tot ++;
ans[x] = tot;
for(auto const &to : e[x]) {
if(to == fa || cal[to])
continue;
dfs3(to,x);
tot ++;
}
for(auto const &to : e[x]) {
if(to == fa || !cal[to])
continue;
dfs3(to,x);
}
}
int main() {
cin >> n;
for(int i = 1,u,v;i < n; i++) {
cin >> u >> v;
e[u].emplace_back(v);
e[v].emplace_back(u);
}
GetCal();
dfs2(EndPoint,0);
dfs3(EndPoint,0);
for(int i = 1;i <= n; i++)
cout << ans[i] << " ";
cout << "\n";
return 0;
}