记录编号	166979	评测结果	AAAAAAAAAA
题目名称	[POJ1741][男人八题]树上的点对	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	1.588 s
提交时间	2015-06-18 10:16:15	内存使用	57.83 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <functional>
#include <vector>
#include <map>
#include <string>
#include <queue>
#include <stack>
using namespace std;
typedef long long LL;
///===================struct declaration======================
struct adj{
	 int to,dist;
	 adj (int to = 0, int dist = 0): to(to), dist(dist){}
};
///===================var declaration=========================
const int MAXN=10010;
int n,k,_Ans,_Sum,SubTreeSize;
int Depth[MAXN],S[MAXN],f[MAXN],A[MAXN * 1500];
bool Del[MAXN];
vector <adj> Edge[MAXN];
///===================function declaration====================
void GetAns(int x);//得出x所在的子树中的答案
void DFS(int x, int fa, int &Sub);//得出depth等信息
void DFS2(int x, int fa, vector <int> &List);//用于合并子树信息
void dp(int x, int fa, int &core);
int Query(int x);int lowbit(int x){return x & -x;}void Add(int x, int Val);
///===================main code===============================
int main(){

	 freopen("poj1741_tree.in","r",stdin);
	 freopen("poj1741_tree.out","w",stdout);

 	 while (scanf("%d%d", &n, &k) != EOF && n){
		  _Ans = 0;memset(Del, false, sizeof(Del));
		  for (int i = 1; i <= n; i++)  Edge[i].clear();
		  for (int i = 1; i < n; i++){
				int u, v, l;scanf("%d%d%d", &u, &v, &l);
				Edge[u].push_back(adj(v, l));
				Edge[v].push_back(adj(u, l));
		  }
		  GetAns(1);
		  printf("%d\n", _Ans);
	 }
	 return 0;
}
///==================function code===========================
void GetAns(int x){
	 Depth[x] = 0;
	 DFS(x, -1, SubTreeSize = 0);
	 f[0] = 1008611;
	 int core = 0;
	 dp(x, -1, core);
	 Depth[core] = 0;
	 DFS(core, -1, SubTreeSize = 0);
	 int siz = Edge[core].size();
	 vector <int> LIST;
	 for(int i = 0; i < siz; i++){
		  adj &e = Edge[core][i];
		  if (Del[e.to]) continue;
		  vector <int> List;List.clear();
		  DFS2(e.to, core, List);
		  int ListSize = List.size();
		  for(int j = 0; j < ListSize; j++){
				Add(List[j], 1);
				LIST.push_back(List[j]);
		  }
	 }
	 int LISTSize = LIST.size();
	 for(int i = 0; i <  LISTSize; i++)
		  Add(LIST[i], -1);
	 Del[core] = true;
	 for(int i = 0; i < siz; i++){
		  adj &e = Edge[core][i];
		  if (Del[e.to]) continue;
		  GetAns(e.to);
	 }
}
void DFS(int x, int fa, int &Sub){
	 int siz = Edge[x].size();
	 S[x] = 1;
	 if (x == 7403){
		  int a = 0 ;
		  a++;
	 }
	 Sub ++;
	 for (int i = 0; i < siz; i++){
		  adj &e = Edge[x][i];
		  if (e.to == fa || Del[e.to]) continue;
		  Depth[e.to] = Depth[x] + e.dist;
		  DFS(e.to, x, Sub);
		  S[x] += S[e.to];
	 }
}
void dp(int x, int fa, int &core){
	 int siz = Edge[x].size();
	 f[x] = SubTreeSize - S[x];
	 for (int i = 0; i < siz; i++){
		  adj &e = Edge[x][i];
		  if (Del[e.to] || e.to == fa) continue;
		  dp(e.to, x, core);
		  f[x] = max(f[x], S[e.to]);
	 }
	 if (f[x] < f[core]) core = x;
}
void DFS2(int x, int fa, vector <int> &List){
	 if (Depth[x] > k) return;
	 _Ans ++;
	 List.push_back(Depth[x]);
	 _Ans += Query(k - Depth[x]);
	 int siz = Edge[x].size();
	 for(int i = 0; i < siz; i++){
		  adj &e = Edge[x][i];
		  if (e.to == fa || Del[e.to]) continue;
		  DFS2(e.to, x, List);
	 }
}
int Query(int x){
	 int res = 0;
	 while (x > 0){
		  res += A[x];
		  x -= lowbit(x);
	 }
	 return res;
}
void Add(int x, int Val){
	 while (x <= k){
		  A[x] += Val;
		  x += lowbit(x);
	 }
}