Croc Champ 2013-Round 2構文

テーマリンク:
泥棒を捕まえて先に王を捕まえて、毎回試合後にCFの問題を総括して、私はすべて先にE題をやることが好きで、その上E題は普通は私の一番好きなデータの構造問題で、やり始めてとてもさわやかです.
E題:木をあげます.距離の和を求めます.
類似のテーマ:http://poj.org/problem?id=1741 
方法は点の分治で、具体的に漆子の超の論文を参考にして、分治のアルゴリズムは木の経路の中の応用で、論文の中ですでにとても詳しく述べました.
poj 1741ができたら、この問題は一つの制限が多くなりました.やはり順序よくスキャンします.でも、求める時は木の形の配列でメンテナンスします.実は簡単です.
つの2つの元のシリーズがどれだけの条件を満たすことに対してあることを求めます時カードはとても長くて、大神達がすべて1つの0をプラスしたのなことを見て、私はプラスしたくなくて、そこで書けば書くほど煩わしくて、少なく計算するのではありませんて、最後に落ち着いて改めて考えて、あれはやはり先に2倍のを計算します.
私のあのcanc関数は少しへこまれました.
poj 1741

#include
#include
#include
#include
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::iterator it = x.begin(); it!=x.end();it++)
vector edge[MAX_N];
int N , K;
int size[MAX_N]  ;
int opt[MAX_N];
bool del[MAX_N] ;
long long  Ans ;
vector  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::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 all , ch[MAX_N];
void Get_dis(int u,int fa,int len,vector &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 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
",Ans);
	}
	return 0;
}

CROC round 2 E

// http://poj.org/problem?id=1741
#include
#include
#include
#include
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::iterator it = x.begin(); it!=x.end();it++)
vector edge[MAX_N];
int N , K;
int size[MAX_N]  ;
int opt[MAX_N];
bool del[MAX_N] ;
long long  Ans ;
vector  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::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 > all , ch[MAX_N];
void Get_dis(int u,int fa,int len,vector > &ch,int sum)
{
	ch.push_back(make_pair(sum,len));
	all.push_back(make_pair(sum,len));
	Tr(it,edge[u])
	{
		if(it->b!=fa && !del[it->b]) {
			Get_dis(it->b,u,len+it->w,ch,sum+1);
		}
	}
}
struct BIT{
	int c[MAX_N];
	int maxn ;
	void init(int n) {
		maxn = n;
		memset(c,0,sizeof(int)*n);
	}
	void insert(int x,int d) {
		for(x++;x<=maxn;x+=x&-x) c[x] += d;
	}
	int sum(int x) {
		int ans = 0;
		for(x++;x;x-=x&-x) ans += c[x];
		return ans;
	}
}bit;
int L , W;
int cmp(pair a, pair b) {
	if(a.second != b.second)return a.second < b.second;
	return a.first < b.first;
}
long long calc(vector > d,bool f) //       ， 
{
 	long long ans  = 0;
	int pt = 0 , sz = d.size();
	int mxd = 0;
	for(int i = 0; i < sz ; i++) {
		mxd = max(mxd,d[i].first);
	}
	bit.init(mxd+2);
	sort(d.begin(),d.end(),cmp);
	int cnt = 0;
	int j = 0;
	for(int i = sz - 1 ; i >= 0; i--) {// cnt :             ，      
		if(f && d[i].first <= L && d[i].second <= W) cnt++;
		while(j < sz && d[j].second + d[i].second <= W) {
			bit.insert(d[j].first,1);
			j++;
		}
	    if(L >= d[i].first){
			ans += bit.sum(min(mxd,L-d[i].first));
			if(j > i) if(d[i].first+d[i].first <= L) ans --; //             ，   
		}
	}
	ans += cnt * 2;
	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 
	Tr(it,edge[u])
	{
		ch[nch].clear(); 
		if(!del[it->b]) Get_dis(it->b,u,it->w,ch[nch++],1);
	}	

	Ans += calc(all,true);
	for(int i = 0; i < nch; i++)  Ans -= calc(ch[i],false);	

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