[USACO2010 Feb Gold 【slowdown】]对树进行“序”的转化、树状数组

【题目链接】http://ace.delos.com/ioiupload?init=1&a=CKerK76g6Pn
or 八中
【题目大意】
给定以1为根的一棵树。点数<=10^5
然后每个点按输入顺序被染色。
每次染色前都输出，从根到该结点的路径上，有多少个点被染色过了？
【算法分析】
首先，假如一个点染色，会影响到哪些点呢？
没错，就是以他为根的子树上的所有点。
所以我们按DFS序遍历的话，会得出一张线性表，在这个表上，每一个点为根的子树就会连在一起~
进而可以用线段树或者树状数组解决。
当然，树状数组好些多了。
【其它】1Y
【CODE】
/*
ID:jie22221
TASK:slowdown
LANG:C++
*/
#include #include #include #include using namespace std;
const int N=105555;
struct edge{int y;edge *next;}*ls[N];
int n,times;
int St[N],Ed[N],w[N];

void addedge(int x,int y){
edge *t=(edge *)malloc(sizeof(edge));
t->y=y; t->next=ls[x]; ls[x]=t;
}

void init(){
memset(ls,0,sizeof(ls));
scanf("%d",&n);
for (int i=1,x,y;i scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
}

void dfs(int p,int fa){
St[p]=++times;
for (edge *t=ls[p];t;t=t->next)
if (t->y!=fa)
dfs(t->y,p);
Ed[p]=times;
}

int Get_Sum(int p){
int res=0;
for (int i=p;i;i-=i&-i)
res+=w[i];
return res;
}

void Add(int p,int x){
for (int i=p;i<=n;i+=i&-i)
w[i]+=x;
}

void solve(){
memset(w,0,sizeof(w));
for (int i=1,x;i<=n;i++){
scanf("%d",&x);
printf("%dn",Get_Sum(St[x]));
Add(St[x],1);
Add(Ed[x]+1,-1);
}
}

int main(){
freopen("slowdown.in","r",stdin);
freopen("slowdown.out","w",stdout);
init();
dfs(1,0);
solve();
return 0;
}