[ POJ 1741 ] Tree

題目:
http://poj.org/problem?id=1741

解法:
樹分治，找出重心後，算出通過重心且長度$\leq k$的路徑有幾個，因為我是所有路徑一起算的，所以還要扣掉在同一個子樹的路徑，算路徑會花$\ord{n log n}$，樹分治深度最多$\ord{log n}$，因此總複雜度是$\ord{n log^2 n}$

code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73

#include<bits/stdc++.h> using namespace std; #define MAXN 10005 int n,k; vector<pair<int,int> >g[MAXN]; int size[MAXN]; bool vis[MAXN]; inline void init(){ for(int i=0;i<=n;++i){ g[i].clear(); vis[i]=0; } } void get_dis(vector<int> &dis,int u,int pa,int d){ dis.push_back(d); for(size_t i=0;i<g[u].size();++i){ int v=g[u][i].first,w=g[u][i].second; if(v!=pa&&!vis[v])get_dis(dis,v,u,d+w); } } vector<int> dis;//這東西如果放在函數裡會TLE int cal(int u,int d){ dis.clear(); get_dis(dis,u,-1,d); sort(dis.begin(),dis.end()); int l=0,r=dis.size()-1,res=0; while(l<r){ while(l<r&&dis[l]+dis[r]>k)--r; res+=r-(l++); } return res; } pair<int,int> tree_centroid(int u,int pa,const int sz){ size[u]=1;//找樹重心，second是重心 pair<int,int> res(INT_MAX,-1); int ma=0; for(size_t i=0;i<g[u].size();++i){ int v=g[u][i].first; if(v==pa||vis[v])continue; res=min(res,tree_centroid(v,u,sz)); size[u]+=size[v]; ma=max(ma,size[v]); } ma=max(ma,sz-size[u]); return min(res,make_pair(ma,u)); } int tree_DC(int u,int sz){ int center=tree_centroid(u,-1,sz).second; int ans=cal(center,0); vis[center]=1; for(size_t i=0;i<g[center].size();++i){ int v=g[center][i].first,w=g[center][i].second; if(vis[v])continue; ans-=cal(v,w); if(size[v]>size[center]) size[v]=sz-size[center]; ans+=tree_DC(v,size[v]); } return ans; } int main(){ while(scanf("%d%d",&n,&k),n||k){ init(); for(int i=1;i<n;++i){ int u,v,w; scanf("%d%d%d",&u,&v,&w); g[u].push_back(make_pair(v,w)); g[v].push_back(make_pair(u,w)); } printf("%d\n",tree_DC(1,n)); } return 0; }