27-28cf

Distance in Tree
这两天只做了一题，因为这一题牵扯到一个新的知识点

题意

给一颗树，问距离为k的有几个不同的点对

解法一：树形DP

代码量少，好理解，好码

注意一般情况下，dp[i][j]代表到i这个点距离为j的有几个

注意点：算答案，再加入dp（我觉得我要不被提醒，一定不会注意

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 5e4 + 10;
ll ans = 0;
ll dp[MAX][550];
vector<ll>G[MAX];
//dp[i][j]代表到i这个点距离为j的有几个
void dfs(ll u, ll fa, ll k) {dp[u][0] = 1;for(int i = 0; i < G[u].size(); i++) {ll v = G[u][i];if(v == fa) continue;dfs(v, u, k);//先算答案，再加入dp//防止子树重复算for(int j = 0; j < k; j++) {ans += dp[u][j] * dp[v][k - j - 1];}for(int j = 0; j < k; j++) {dp[u][j] += dp[v][j - 1];}}
}
int main() {ll n, k;scanf("%lld%lld", &n, &k);for(int i = 1; i < n; i++) {ll a, b;scanf("%lld %lld", &a, &b);G[a].push_back(b);G[b].push_back(a);}dfs(1, -1, k);printf("%lld\n", ans);
}

解法二：树分治

可以解权值不为1的情况

新的知识点，代码还需再熟悉

板子也要整理！！

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const ll MAXN = 100005;
const ll INF = 1e9 + 7;struct edge {ll to, length;edge() {}edge(ll a, ll b) : to(a), length(b) {}
};vector<edge> G[MAXN];
bool centroid[MAXN];
ll subtree_size[MAXN];
ll ans, k;//计算子树大小
ll compute_subtree_size(ll v, ll fa) {ll sizee = 1;for(int i = 0; i < G[v].size(); i++) {ll u = G[v][i].to;if(u == fa || centroid[u]) continue;sizee += compute_subtree_size(u, v);}subtree_size[v] = sizee;return sizee;
}//查找重心，t为连通分量大小
// pair（最大子树顶点数，顶点编号）
pair<ll, ll> search_centroid(ll v, ll fa, ll sum) {pair<ll, ll> res = pair<ll, ll>(INF, -1);ll  s = 1, m = 0;for(int i = 0; i < G[v].size(); i++) {ll u = G[v][i].to;if(u == fa || centroid[u]) continue;res = min(res, search_centroid(u, v, sum));m = max(m, subtree_size[u]);s += subtree_size[u];}m = max(m, sum - s);res = min(res, pair<ll,ll>(m, v));return res;
}void init(ll n) {memset(centroid, 0, sizeof centroid);memset(subtree_size, 0, sizeof subtree_size);for(int i = 0; i <= n; i++) {G[i].clear();}ans = 0;
}void dfs1(ll v, ll fa, ll d, unordered_map<ll, ll> &mp) {ans += mp[k - d];for (auto x:G[v]) {if (x.to == fa || centroid[x.to]) continue;dfs1(x.to, v, d + x.length, mp);}
}void dfs2(ll v, ll fa, ll d, unordered_map<ll, ll> &mp) {mp[d]++;for (auto x:G[v]) {if (x.to == fa || centroid[x.to]) continue;dfs2(x.to, v, d + x.length, mp);}
}ll solve(ll v) {compute_subtree_size(v, -1);ll cen = search_centroid(v,  -1, subtree_size[v]).second;centroid[cen] = 1;unordered_map<ll, ll> mp;mp[0] = 1;for(ll i = 0; i < G[cen].size(); i++) {ll u = G[cen][i].to;if(centroid[u]) continue;solve(u);}for(ll i = 0; i < G[cen].size(); i++) {ll u = G[cen][i].to;if(centroid[u]) continue;//xdfs1(u, cen, G[cen][i].length, mp);dfs2(u, cen, G[cen][i].length, mp);}centroid[cen] = 0;return ans;
}int main() {ll n;scanf("%lld%lld", &n, &k);init(n);for (ll i = 1; i < n; i++) {ll a, b;scanf("%lld%lld", &a, &b);G[a].push_back({b, 1});G[b].push_back({a, 1});}solve(1);printf("%lld\n", ans);
}