10.21 模拟赛 猴猴的比赛（树状数组）

满分做法：

在第一棵树中确定编号的dfs序，遍历第二棵树时，用树状数组维护在第一棵树相对位置，查询某点的贡献时，统计有多少比他高的就行了。注意要在子树后消除影响。

#include<cstring>
#include<queue>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
int n;
const int maxm=200007;
int pre[maxm],last[maxm],other[maxm],l;
int id[maxm],cnt,son[maxm],size[maxm],f[maxm];
int pre1[maxm],last1[maxm],other1[maxm],l1;
int c[maxm];
int ans=0;
void add(int x,int y)
{
 l++;
 pre[l]=last[x];
 last[x]=l;
 other[l]=y;
}
void add1(int x,int y)
{
 l1++;
 pre1[l1]=last1[x];
 last1[x]=l1;
 other1[l1]=y;
}
void dfs(int x,int fa)
{
 size[x]=1;
 f[x]=fa;
 for(int p=last[x];p;p=pre[p])
 {
   int v=other[p];
   if(v==fa) continue;
   dfs(v,x);
   size[x]+=size[v];
   if(size[son[x]]<size[v])
   son[x]=v;
 }
}
void dfs1(int x)
{
 ++cnt;
 id[x]=cnt;
 if(!son[x]) return;
 dfs1(son[x]);
 for(int p=last[x];p;p=pre[p])
 {
  int v=other[p];
  if(v==f[x]||v==son[x]) continue;
  dfs1(v);
 }
}
int lowbit(int x)
{
 return x&(-x);    
}
void change(int x,int y)
{
 for(;x<=n;x+=lowbit(x))
 {
   c[x]+=y;
 }
}
int query(int x)
{
  int tmp=0;
  for(;x;x-=lowbit(x))
  tmp+=c[x];
  return tmp;    
}
void dfs2(int x,int fa)
{
 int tmp=query(id[x]);
 change(id[x],1);
 change(id[x]+size[x],-1);
 ans=ans+tmp;
 for(int p=last1[x];p;p=pre1[p])
 {
  int v=other1[p];
  if(v==fa) continue;
  dfs2(v,x); 
 }
 change(id[x],-1);
 change(id[x]+size[x],1);
}
int main()
{
 freopen("climb.in","r",stdin);
 freopen("climb.out","w",stdout);
 scanf("%d",&n);
 for(int i=1;i<=n-1;i++)
 {
  int x,y;
  scanf("%d%d",&x,&y);
  add(x,y);
  add(y,x);    
 }
 dfs(1,0);
 dfs1(1);
 for(int i=1;i<=n-1;i++)
 {
  int x,y;
  scanf("%d%d",&x,&y);
  add1(x,y);
  add1(y,x);    
 }
 dfs2(1,0);
 printf("%d
",ans);
 return 0;    
}