1 条题解
-
0
换根DP板子题,用换根计算每个点到叶子节点的距离即可。
时间复杂度:
const int maxn = 2e5 + 7; int n, k; vector<int> edge[maxn]; int siz[maxn], sum[maxn]; void dfs(int x, int z) { siz[x] = (edge[x].size() == 1); sum[x] = 0; for (int y : edge[x]) { if (y == z) continue; dfs(y, x); siz[x] += siz[y]; sum[x] += sum[y] + siz[y]; } } int dis[maxn]; void dfs2(int x, int z) { if (x != 1) dis[x] = dis[z] + (siz[1] - siz[x]) - siz[x]; else dis[x] = sum[x]; for (int y : edge[x]) { if (y == z) continue; dfs2(y, x); } } void solve() { cin >> n >> k; for (int i = 1; i < n; i++) { int x, y; cin >> x >> y; edge[x].push_back(y); edge[y].push_back(x); } dfs(1, 0); dfs2(1, 0); for (int i = 1; i <= k; i++) { int x; cin >> x; cout << dis[x] << endl; } }
- 1
信息
- ID
- 17
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 2
- 已通过
- 2
- 上传者