题目链接：http://www.lydsy.com:808/JudgeOnline/problem.phpid=1103
题目大意：给你一个树，刚开始所有树边边权均为1，不断地将其中的某些边边权改为0，其间问你某个点到根节点之间路径上的边权和。
此题和POJ的Apple Tree很相近。。。
首先DFS生成整棵树的拓扑序，DFS时每个结点i进入的时间l[i]和离开的时间r[i]，然后对每次更改操作，维护树状数组即可。
#include
#include
#include
#include
#include
#define MAXE 501000 #define MAXV 251000 #define lowbit(x) (x&(-x)) using namespace std; struct edge { int u,v,next; }edges[MAXE]; int head[MAXV],nCount=0; int sum[MAXE],cnt=0,l[MAXV],r[MAXV],fa[MAXV]; //l、r是每个结点dfs序的左右区间 int n,m; bool visit[MAXV]; void AddEdge(int U,int V) { edges[++nCount].u=U; edges[nCount].v=V; edges[nCount].next=head[U]; head[U]=nCount; } void update(int x,int v) { while(x
0) { ans+=sum[x]; x-=lowbit(x); } return ans; } void dfs(int u) //从点u出发dfs，得到树的拓扑序 { visit[u]=true; l[u]=++cnt; update(cnt,1); for(int p=head[u];p!=-1;p=edges[p].next) { int v=edges[p].v; if(!visit[v]) { fa[v]=u; dfs(v); } } r[u]=++cnt; update(cnt,-1); } int main() { memset(head,-1,sizeof(head)); char cmd[10]; scanf("%d",&n); for(int i=1;i