Croc Champ 2013 - Round 2 题解

题目链接：

擒贼先擒王，每次赛后总结CF的题，我都喜欢先搞E题，而且E题一般是我最爱的数据结构题，搞起来特爽

E题：给你一棵树，求满足距离之和<=L 且路径上的权值之和<= w的点对数量。。。

方法是点的分治，具体参考漆子超的论文，分治算法在树的路径中的应用，论文里面已经讲了很详细了

会了poj 1741的话，其实这道题就是多了一个限制，还是排序，扫描，不过在求的时候需要用树状数组维护一下，其实很简单，不过我还是调试了很久，，，，，代码能力与思维能力都需要精雕细琢啊。

在求一个二元组序列有多少对满足条件时卡了很久，看大神们都是加了一个0 0进去，我就是不想加，于是越写越烦，不是少算就是多算，最后冷静下来重新想了想，那还是先算成两倍的吧

我的那个calc函数略挫，，，，

poj 1741

[cpp]
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX_N = 100010;
struct Edge{
    int b , w;
    Edge() {}
    Edge(int b,int w): b(b),w(w){
    }
};
#define Tr(it,x) for(vector<Edge>::iterator it = x.begin(); it!=x.end();it++)
vector<Edge> edge[MAX_N];
int N , K;
int size[MAX_N] ;
int opt[MAX_N];
bool del[MAX_N] ;
long long Ans ;
vector<int> tnode;
void Dfs(int u,int fa)
{
    tnode.push_back(u);
    opt[u] = 0;
    size[u] = 1;
    Tr(it,edge[u])
    {
        int v = it->b;
        if(!del[v] && v!=fa){
            Dfs(v , u);
            opt[u] = max(opt[u],size[v]);
            size[u] += size[v];
        }
    }
}
int Find(int u) // find the centre of gravity
{
    Dfs(u,-1);
    int who = -1 , mx = MAX_N;
    for(vector<int>::iterator it = tnode.begin(); it != tnode.end(); it++)
    {
        opt[*it] = max(opt[*it],size[u]-size[*it]);
        if(mx > opt[*it]) {
            mx = opt[*it];
            who = *it;
        }
    }
    return who;
}
vector<int> all , ch[MAX_N];
void Get_dis(int u,int fa,int len,vector<int> &ch)
{
    ch.push_back(len);
    all.push_back(len);
    Tr(it,edge[u])
    {
        if(it->b!=fa && !del[it->b]) {
            Get_dis(it->b,u,len+it->w,ch);
        }
    }
}
long long calc(vector<int> dist)
{
    long long ans = 0;
    int pt = 0 , sz = dist.size();
    sort(dist.begin(),dist.end());
    for(int i = 0,j = sz - 1;i <= j;i++)
    {
        while(i <= j && dist[i] + dist[j] > K) {
            j--;
        }
        if(i < j) ans += j - i;
    }
    return ans;
}
void Solve(int u)
{
    tnode.clear();
    u = Find(u); // the gravity center
    all.clear(); // all of the distances
    int nch = 0; // count of sons
    all.push_back(0);
    Tr(it,edge[u])
    {
        ch[nch].clear();
        if(!del[it->b]) Get_dis(it->b,u,it->w,ch[nch++]);
    }
    Ans += calc(all);
    for(int i = 0; i < nch; i++) Ans -= calc(ch[i]);

    del[u] = true;
    Tr(it,edge[u])
        if(!del[it->b]) Solve(it->b);
}
int main()
{
    int a,b,w;
    while(scanf("%d%d",&N,&K),N||K)
    {
         for(int i = 1; i <= N; i++) edge[i].clear(),del[i]=false;
         for(int i = 1; i < N; i++)
         {
             scanf("%d%d%d",&a,&b,&w);
             edge[a].push_back(Edge(b,w));
             edge[b].push_back(Edge(a,w));
         }
         Ans = 0;
         Solve(1);
         printf("%I64d\n",Ans);
    }
    return 0;
}

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX_N = 100010;
struct Edge{
int b , w;
Edge() {}
Edge(int b,int w): b(b),w(w){
}
};
#define Tr(it,x) for(vector<Edge>::iterator it = x.begin(); it!=x.end();it++)
vector<Edge> edge[MAX_N];
int N , K;
int size[MAX_N] ;
int opt[MAX_N];
bool del[MAX_N] ;
long long Ans ;
vector<int> tnode;
void Dfs(int u,int fa)
{
tnode.push_back(u);
opt[u] = 0;
size[u] = 1;
Tr(it,edge[u])
{
  int v = it->b;
  if(!del[v] && v!=fa){
   Dfs(v , u);
   opt[u] = max(opt[u],size[v]);
   size[u] += size[v];
  }
}
}
int Find(int u) // find the centre of gravity
{
Dfs(

补充：软件开发 , C++ ,