[POJ 1741][男人八題][樹分治] Tree

題目連結

不多說......就是樹分治的經典問題......在那個科技還不發達的年代還是挺難做的......

找重心，分治計算答案。最難的地方大概是答案的加減要想清楚，不然很容易完全寫錯。

啟發式合併貌似也挺快的，晚點補上code。

#include<cstdio>
#include<vector>
#include<algorithm>
#include<string.h>
using namespace std;
const int INF=(1<<30);
const int maxn=10000+5;
struct Edge{int from,to,w;};
vector<Edge> edges;
vector<int> G[maxn],vec;
int ans,root,N,k,center,dp[maxn],size[maxn],done[maxn];
void getdis(int now,int fa,int depth)
{
    vec.push_back(depth);
    for(int i=0;i<G[now].size();i++)
    {
        Edge& e=edges[G[now][i]];
        int to=e.to==now?e.from:e.to;
        if(to!=fa && !done[to]) getdis(to,now,depth+e.w);
    }
}
void getsize(int now,int fa)
{
    size[now]=1;dp[now]=0;
    for(int i=0;i<G[now].size();i++)
    {
        Edge& e=edges[G[now][i]];
        int to=e.to==now?e.from:e.to;
        if(to!=fa && !done[to]) {getsize(to,now);size[now]+=size[to];dp[now]=max(dp[now],size[to]);}
    }
}
void findc(int now,int fa)
{
    dp[now]=max(size[root]-size[now],dp[now]);
    if(dp[now]<dp[center]) center=now; 
    for(int i=0;i<G[now].size();i++)
    {
        Edge& e=edges[G[now][i]];
        int to=e.to==now?e.from:e.to;
        if(to!=fa && !done[to]) findc(to,now);
    }
}
int calc(int now,int d)
{
    int ret=0;
    vec.clear();
    getdis(now,-1,d);
    
    sort(vec.begin(),vec.end());
    int R=vec.size()-1;
    for(int L=0;L<vec.size();L++)
    {
        while(R && vec[L]+vec[R]>k) R--;
        if(R<=L) break;
        ret+=R-L;
    }
    return ret;
}
void DAC(int now)
{
    root=now;getsize(now,-1);
    center=now;findc(now,-1);
    
    int c=center;
    ans+=calc(c,0);
    done[c]=1;
    for(int i=0;i<G[c].size();i++)
    {
        Edge& e=edges[G[c][i]];
        int to=e.to==c?e.from:e.to;
        if(done[to]) continue;
        ans-=calc(to,e.w);
        DAC(to);
    }
}
void solve()
{
    memset(done,0,sizeof done);
    ans=0;DAC(0);
    printf("%d\n",ans);
}
int main()
{
    while(scanf("%d%d",&N,&k)==2 && N&&k)
    {
        edges.clear();
        for(int i=0;i<N;i++) G[i].clear();
        for(int i=0,a,b,c;i<N-1;i++) {scanf("%d%d%d",&a,&b,&c);a--,b--;edges.push_back((Edge){a,b,c});G[a].push_back(edges.size()-1);G[b].push_back(edges.size()-1);}
        solve();
    }
}