Homework Introduction

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, f[N], d[N], d2[N];
vector<int>e[N];

void dfs(int x, int fa) {
	for (auto v : e[x]) {
		if (v == fa)
			continue;
		dfs(v, x);
		if (d[v] + 1 > d[x]) {
			d2[x] = d[x];
			d[x] = d[v] + 1;
		} else if (d[v] + 1 > d2[x]) {
			d2[x] = d[v] + 1;
		}
	}
}

int main() {
	cin >> n;
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs(1, 0);
	int res = 0;
	for (int i = 1; i <= n; i++) {
		res = max(res, d[i] + d2[i]);
	}
	cout << res << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m, fa[N][25], dep[N];
vector<int>e[N];

void dfs(int x, int f, int deep) {
	dep[x] = deep;
	fa[x][0] = f;
	for (int j = 1; j <= 20; j++) {
		fa[x][j] = fa[fa[x][j - 1]][j - 1];
	}
	for (auto v : e[x]) {
		if (v == f)
			continue;
		dfs(v, x, deep + 1);
	}
}

int lca(int x, int y) {
	if (dep[x] > dep[y])
		swap(x, y);
	//1.让y与x同层
	for (int j = 20; j >= 0; j--) {
		if (dep[fa[y][j]] >= dep[x])
			y = fa[y][j];
	}
	if (x == y)
		return x;
	for (int j = 20; j >= 0; j--) {
		if (fa[x][j] != fa[y][j]) {
			x = fa[x][j];
			y = fa[y][j];
		}
	}
	return fa[x][0];
}

int main() {
	cin >> n >> m;
	for (int i = 2; i <= n; i++) {
		int x;
		cin >> x;
		e[x].push_back(i);
		e[i].push_back(x);
	}
	dfs(1, 0, 1);
	while (m--) {
		int x, y;
		cin >> x >> y;
		cout << lca(x, y) << "\n";
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m, siz[N], dep[N], fa[N], son[N];
int top[N];
vector<int>e[N];

void dfs1(int x, int f, int deep) {
	dep[x] = deep;
	fa[x] = f;
	siz[x] = 1;
	int maxx = 0;
	for (auto v : e[x]) {
		if (v == f)
			continue;
		dfs1(v, x, deep + 1);
		siz[x] += siz[v];
		if (siz[v] > maxx) {
			maxx = siz[v];
			son[x] = v;
		}
	}
}

void dfs2(int x, int topfa) {
	top[x] = topfa;
	if (!son[x])
		return;
	dfs2(son[x], topfa);
	for (auto v : e[x]) {
		if (v == son[x] || v == fa[x])
			continue;
		dfs2(v, v);
	}
}

int lca(int x, int y) {
	while (top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]])
			swap(x, y);
		x = fa[top[x]];
	}
	if (dep[x] > dep[y])
		swap(x, y);
	return x;
}

int main() {
	cin >> n >> m;
	for (int i = 2; i <= n; i++) {
		int x;
		cin >> x;
		e[x].push_back(i);
		e[i].push_back(x);
	}
	dfs1(1, 0, 1);
	dfs2(1, 1);
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		cout << lca(x, y) << endl;
	}
	return 0;
}

//sum[a]+sum[b]-2*sum[lca]
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m, fa[N][25], dep[N], dis[N], b[N];
vector<int>e[N];

void dfs(int x, int f, int deep) {
	dep[x] = deep;
	fa[x][0] = f;

	for (int j = 1; j <= 20; j++) {
		fa[x][j] = fa[fa[x][j - 1]][j - 1];
	}
	for (auto v : e[x]) {
		if (v == f)
			continue;
		dis[v] = dis[x] + 1;
		dfs(v, x, deep + 1);
	}
}

int lca(int x, int y) {
	if (dep[x] > dep[y])
		swap(x, y);
	for (int j = 20; j >= 0; j--) {
		if (dep[fa[y][j]] >= dep[x])
			y = fa[y][j];
	}
	if (x == y)
		return x;
	for (int j = 20; j >= 0; j--) {
		if (fa[x][j] != fa[y][j]) {
			y = fa[y][j];
			x = fa[x][j];
		}
	}
	return fa[x][0];
}

void dfs2(int x, int fa) {
	for (auto v : e[x]) {
		if (v == fa)
			continue;
		dfs2(v, x);
		b[x] += b[v];
	}
}

int main() {
	cin >> n >> m;
	for (int i = 2; i <= n; i++) {
		int x, y;
		cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs(1, 0, 1);
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		b[x]++;
		b[y]++;
		int LCA = lca(x, y);
		b[LCA]--;
		b[fa[LCA][0]]--;
	}
	dfs2(1, 0);
	for (int i = 1; i <= n; i++) {
		cout << b[i] << " ";
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int n, m, a[N];
vector<int>e[N];
int siz[N], dep[N], son[N], fa[N];
int w[N], id[N], top[N], cnt;
int tree[N << 2];

void dfs1(int x, int f, int deep) {
	fa[x] = f;
	dep[x] = deep;
	siz[x] = 1;
	int maxx = 0;
	for (auto v : e[x]) {
		if (v == f)
			continue;
		dfs1(v, x, deep + 1);
		siz[x] += siz[v];
		if (siz[v] > maxx) {
			son[x] = v;
			maxx = siz[v];
		}
	}
}

void dfs2(int x, int topfa) {
	id[x] = ++cnt;
	w[cnt] = a[x];
	top[x] = topfa;
	if (!son[x])
		return;
	dfs2(son[x], topfa);
	for (auto v : e[x]) {
		if (v == fa[x] || v == son[x])
			continue;
		dfs2(v, v);
	}
}

void pushup(int rt) {
	tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}

void build(int l, int r, int rt) {
	if (l == r) {
		tree[rt] = w[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, rt << 1);
	build(mid + 1, r, rt << 1 | 1);
	pushup(rt);
}

void update(int l, int r, int rt, int p, int c) {
	if (l == r) {
		tree[rt] = c;
		return;
	}
	int mid = (l + r) >> 1;
	if (p <= mid)
		update(l, mid, rt << 1, p, c);
	else
		update(mid + 1, r, rt << 1 | 1, p, c);
	pushup(rt);
}

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

int pos1(int x, int y) {
	int res = 0;
	while (top[x] != top[y]) {
		if (dep[top[x]] > dep[top[y]])
			swap(x, y);
		res += query(1, n, 1, id[top[y]], id[y]);
		y = fa[top[y]];
	}
	if (dep[x] > dep[y])
		swap(x, y);
	res += query(1, n, 1, id[x], id[y]);
	return res;
}

signed main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs1(1, 0, 1);
	dfs2(1, 1);
	build(1, n, 1);
	for (int i = 1; i <= m; i++) {
		int pos, x, y, z;
		cin >> pos >> x;
		if (pos == 1) {
			cin >> y;
			update(1, n, 1, id[x], y);
		} else {
			cout << pos1(1, x) << endl;
		}
	}
	return 0;
}

/*
f[x]以x为根，向下走的最大距离
g[x]从x向上走的最大距离

f[x][0] = max(f[v]+1)
f[x][1]
son[x][0] 最大值对应的儿子
son[x][1] 次大致对应的儿子
g[x]
1.向上走到fa[x]再向下走
2.从fa[x]向上走 g[fa]+1
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, dis[N][2], g[N], son[N][2], f[N];
vector<int>e[N];
void dfs1(int x, int fa) {
	for (auto v : e[x]) {
		if (v == fa)
			continue;
		dfs1(v, x);
		if (dis[v][0] + 1 >= dis[x][0]) {
			dis[x][1] = dis[x][0];
			son[x][1] = son[x][0];
			dis[x][0] = dis[v][0] + 1;
			son[x][0] = v;
		} else if (dis[v][0] + 1 > dis[x][1]) {
			dis[x][1] = dis[v][0] + 1;
			son[x][1] = v;
		}
	}
}

void dfs2(int x, int fa) {
	if (x == 1) {
		g[x] = 0;
		f[x] = dis[x][0];
	} else {
		f[x] = dis[x][0];
		if (son[fa][0] == x)
			g[x] = max(g[fa] + 1, 1 + dis[fa][1]);
		else {
			g[x] = max(g[fa] + 1, 1 + dis[fa][0]);
		}
		f[x] = max(f[x], g[x]);
	}
	for (auto v : e[x]) {
		if (v == fa)
			continue;
		dfs2(v, x);
	}
}

int main() {
	cin >> n;
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs1(1, 0);
	dfs2(1, 0);
	for (int i = 1; i <= n; i++) {
		cout << f[i] << " ";
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int n, res, siz[N], f[N], dis[N];
vector<int>e[N];

void dfs1(int x, int fa) {
	siz[x] = 1;
	for (auto v : e[x]) {
		if (v == fa)
			continue;
		dis[v] = dis[x] + 1;
		dfs1(v, x);
		siz[x]+=siz[v];
	}
}

void dfs2(int x, int fa) {
	for (auto v : e[x]) {
		if (v == fa)
			continue;
		f[v] = f[x] - siz[v] + (n - siz[v]);
		dfs2(v, x);
	}
}

signed main() {
	cin >> n;
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs1(1, 0);
	for (int i = 1; i <= n; i++) {
		f[1] += dis[i];
	}
	dfs2(1, 0);
	for (int i = 1; i <= n; i++) {
		cout << f[i] << " ";
	}
	return 0;
}

Problem

Please claim the assignment to see the problems.
Status
Live...
Problem
22
Open Since
2025-10-3 0:00
Deadline
2025-12-31 23:59
Extension
24 hour(s)
  1. Judging Queue
  2. Service Status
  3. Legacy mode
  4. Theme
  2. 蜀ICP备2022005482号-4
  3. Worker 0, 21ms
  4. Powered by Hydro v5.0.0-beta.9 Community