题目链接：https://codeforces.com/contest/161/problem/D
题目大意，求树上路径长度为K的路径条数。 （k<=500)
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/hash_policy.hpp> #define rep(i, a, b) for(int i = (a); i <= (b); i++) #define pb push_back #define ll long long using namespace std; using namespace __gnu_pbds; const int N = 5e4+1000; int n,k; struct node { int v,nxt; }edge[2*N]; int tot,head[N]; void ae(int u,int v) { edge[++tot] = node{v,head[u]}; head[u] = tot; } void init(int n) { tot = 0; rep(i, 1, n) head[i] = -1; } int siz[N],Root,wt[N],Tsiz; bool vis[N]; ll ans; gp_hash_table<int,int> num; void GetRoot(int u,int f) { siz[u] = 1; wt[u] = 0; for(int i = head[u]; ~i ; i = edge[i].nxt) { int v = edge[i].v; if(v==f||vis[v]) continue; GetRoot(v,u); siz[u] += siz[v]; wt[u] = max(wt[u],siz[v]); } wt[u] = max(wt[u],Tsiz-siz[u]); if(wt[Root]>wt[u]) Root = u; } void dfs(int u,int f,int dis) { num[dis]++; for(int i = head[u]; ~i ; i = edge[i].nxt) { int v = edge[i].v; if(v==f||vis[v]) continue; dfs(v,u,dis+1); } } void calc(int u,int dis,int sgn) { num.clear(); dfs(u,0,dis); for(auto x:num) if(x.first<=k/2) { if(x.first*2==k) ans += 1ll*sgn*x.second*(x.second-1)/2; else ans += 1ll*sgn*x.second*num[k-x.first]; } } void divide(int u) { calc(u,0,1); vis[u] = 1; for(int i = head[u]; ~i ; i = edge[i].nxt) { int v = edge[i].v; if(vis[v]) continue; calc(v,1,-1); Root = 0,Tsiz = siz[v]; GetRoot(v,0); divide(Root); } } int main() { //freopen("a.txt","r",stdin); //ios::sync_with_stdio(0); scanf("%d%d",&n,&k); init(n); rep(i, 1, n-1) { int u,v; scanf("%d%d",&u,&v); ae(u,v); ae(v,u); } rep(i, 1, n) vis[i] = 0; wt[0] = 1e9,Tsiz = n,GetRoot(1,0),ans = 0; divide(Root); printf("%I64d\n",ans); return 0; }写法二：
void dfs(int u,int f,int dis) { if(dis>500) return; num[dis]++; for(int i = head[u]; ~i ; i = edge[i].nxt) { int v = edge[i].v; if(v==f||vis[v]) continue; dfs(v,u,dis+1); } } void calc(int u) { rep(i, 0, 500) Tnum[i] = 0; Tnum[0] = 1; //注意，这里并没有考虑u->u这条路径 for(int i = head[u]; ~i ; i = edge[i].nxt) { int v = edge[i].v; if(vis[v]) continue; rep(i, 0, 500) num[i] = 0; dfs(v,u,1); rep(i, 0 ,500) { if(k-i<0) continue; ans += 1ll*num[i]*Tnum[k-i]; } rep(i, 0 ,500) Tnum[i] += num[i]; } } void divide(int u) { calc(u); vis[u] = 1; //删掉该点 for(int i = head[u]; ~i ; i = edge[i].nxt) { int v = edge[i].v; if(vis[v]) continue; Root = 0,Tsiz = siz[v]; GetRoot(v,0); divide(Root); } }
