记录编号	89071	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2004] 树的果实	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.485 s
提交时间	2014-02-28 14:48:20	内存使用	5.28 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<map>
using namespace std;
const int SIZEN=100100;
int N;
int father[SIZEN]={0};
vector<int> c[SIZEN];//儿子
int delic[SIZEN]={0};//美味值
int numpst[SIZEN]={0};//子树上节点个数
int A[SIZEN]={0},B[SIZEN]={0},C[SIZEN]={0};//分别对应三个答案
//即:上面部分(子树),下面部分(除了子树),树根到该点路径中更美味的果子个数
map<int,int> dlcmp;//离散化后的美味值
int numval;//不同美味值的个数
int dfn[SIZEN]={0};//时间戳
class TARRAY{//树状数组
public:
	int n;//范围1~n
	int s[SIZEN];
	void clear(int x){memset(s,0,sizeof(s)),n=x;}
	int lowbit(int x){return x&(-x);}
	int prefsum(int x){//前缀和
		int ans=0;
		for(int i=x;i>0;i-=lowbit(i)) ans+=s[i];
		return ans;
	}
	int segsum(int x,int y){//区间[x,y]的和
		if(x>y) return 0;
		return prefsum(y)-prefsum(x-1);
	}
	void change(int x,int t){//第x个元素+t
		for(int i=x;i<=n;i+=lowbit(i)) s[i]+=t;
	}
};
TARRAY tree;//树状数组
pair<int,int> sorted[SIZEN];//first是美味值,second是位置
void work(void){
	tree.clear(N);
	for(int i=1;i<=N;i++) sorted[i]=make_pair(delic[i],i);
	sort(sorted+1,sorted+1+N);
	for(int i=N;i>=1;){
		int j;
		for(j=i;sorted[j].first==sorted[i].first;j--){
			int x=sorted[j].second;
			A[x]=tree.segsum(dfn[x],dfn[x]+numpst[x]-1);
			B[x]=tree.segsum(1,N)-A[x];
		}
		for(;i>j;i--) tree.change(dfn[sorted[i].second],1);
	}
}
int tim=0;//时间
void DFS(int x){
	tim++;
	dfn[x]=tim;
	C[x]=tree.segsum(delic[x]+1,numval);
	tree.change(delic[x],1);
	numpst[x]=1;//子树上节点个数
	for(int i=0;i<c[x].size();i++){
		DFS(c[x][i]);
		numpst[x]+=numpst[c[x][i]];
	}
	tree.change(delic[x],-1);
}
void init(void){
	scanf("%d",&N);
	for(int i=2;i<=N;i++){
		scanf("%d",&father[i]);
		c[father[i]].push_back(i);
	}
	vector<int> atp;
	for(int i=1;i<=N;i++) scanf("%d",&delic[i]),atp.push_back(delic[i]);
	sort(atp.begin(),atp.end());
	numval=0;
	for(int i=0;i<atp.size();i++) if(!i||atp[i]!=atp[i-1]) dlcmp[atp[i]]=++numval;//离散化
	for(int i=1;i<=N;i++) delic[i]=dlcmp[delic[i]];//修改美味值
	tree.clear(numval);//以权值为下标的树状数组
}
int main(){
	freopen("treesfruits.in","r",stdin);
	freopen("treesfruits.out","w",stdout);
	init();
	DFS(1);
	work();
	for(int i=1;i<=N;i++) printf("%d %d %d\n",A[i],B[i],C[i]);
	return 0;
}