\(\\\)
给出一棵 \(N\) 个点的树和 \(N\) 头牛，每头牛都要去往一个节点，且每头牛去往的点一定互不相同。
现在按顺序让每一头牛去往自己要去的节点，定义一头牛的代价为，路径上经过的已经有牛的节点数，求每一头牛的代价。
- \(N\le 10^5\)
\(\\\)
\(Solution\)
注意到一个节点的影响只是在其子树内，考虑 \(DFS\) 的时候直接统计答案。
在每个节点上记录到这个点的牛的编号。那么对当前点有影响的点满足：
- 在根到这个点的路径上\((\) 是当前点的祖先\()\)
- 编号比这个点小
关于第二点，我们可以用值域树状数组通常的打标记求前缀和的方式知道个数。
但是我们要保证树状数组里只有根到当前点这一条链上的所有点。
这个部分可以通过撤销标记实现，即 \(DFS\) 完整棵子树之后在树状数组里撤销标记。
\(\\\)
\(Code\)
#include#include #include #include #include #include #include #define N 100010#define R register#define gc getcharusing namespace std;inline int rd(){ int x=0; bool f=0; char c=gc(); while(!isdigit(c)){if(c=='-')f=1;c=gc();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();} return f?-x:x;}int n,m,tot,hd[N],p[N],ans[N];struct edge{int to,nxt;}e[N<<1];inline void add(int u,int v){ e[++tot].to=v; e[tot].nxt=hd[u]; hd[u]=tot;}struct BIT{ int c[N]; inline int lowbit(int x){return x&-x;} inline void add(int p,int x){for(;p<=n;p+=lowbit(p))c[p]+=x;} inline int sum(int p){ int res=0; for(;p;p-=lowbit(p)) res+=c[p]; return res; }}bit;inline void dfs(int u,int fa){ ans[p[u]]=bit.sum(p[u]); bit.add(p[u],1); for(R int i=hd[u],v;i;i=e[i].nxt) if((v=e[i].to)!=fa) dfs(v,u); bit.add(p[u],-1);}int main(){ n=rd(); for(R int i=1,u,v;i