标题效果：鉴于一棵树和一个整数s，问中有树木几个这样的路径，点和担保路径＝＝s，深度增量点。

这一数额的输出。

思维：用加倍的想法，我们可以O(logn)在时间找点他第一n。因为点权仅仅能是正的，满足二分性质。然后对于每个点二分。看看有没有路径的权值和是S。统计答案，输出。

CODE：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define MAX 100010

using namespace std;

int points,s;

int src[MAX];

int head[MAX],total;

int next[MAX << 1],aim[MAX << 1];

int father[MAX][20],length[MAX][20];

inline void Add(int x,int y);

void DFS(int x,int last);

void SparseTable();

inline bool Judge(int x);

inline int GetLength(int x,int deep);

int main()

{

	cin >> points >> s;

	for(int i = 1;i <= points; ++i)

		scanf("%d",&src[i]);

	for(int x,y,i = 1;i < points; ++i) {

		scanf("%d%d",&x,&y);

		Add(x,y),Add(y,x);

	}

	DFS(1,0);

	SparseTable();

	int ans = 0;

	for(int i = 1;i <= points; ++i)

		ans += Judge(i);

	cout << ans << endl;

	return 0;

}

inline void Add(int x,int y)

{

	next[++total] = head[x];

	aim[total] = y;

	head[x] = total;

}

void DFS(int x,int last)

{

	father[x][0] = last;

	length[x][0] = src[last];

	for(int i = head[x];i;i = next[i]) {

		if(aim[i] == last)	continue;

		DFS(aim[i],x);

	}

}

void SparseTable()

{

	for(int j = 1;j <= 19; ++j)

		for(int i = 1;i <= points; ++i) {

			father[i][j] = father[father[i][j - 1]][j - 1];

			length[i][j] = length[i][j - 1] + length[father[i][j - 1]][j - 1];

		}

}

inline bool Judge(int x)

{

	int l = 0,r = 100000;

	while(l <= r) {

		int mid = (l + r) >> 1;

		int length = GetLength(x,mid) + src[x];

		if(length < s)	l = mid + 1;

		else if(length > s)	r = mid - 1;

		else	return true;

	}

	return false;

}

inline int GetLength(int x,int deep)

{

	int re = 0;

	for(int i = 19; ~i; --i)

		if(deep - (1 << i) >= 0) {

			deep -= 1 << i;

			re += length[x][i];

			x = father[x][i];

		}

	return re;

}