[JLOI2014]松鼠的新家

题目大意：
　　给你一棵n个结点的带点权的树，指定访问结点的顺序。
　　每次访问走最短路径，并将经过结点的点权+1。
　　问最后各个结点的点权。

思路：
　　树链剖分。
　　每次访问求一下LCA即可，同时维护一下线段树。
　　因为最后只需要统计一次，中间没有询问，因此可以最后在处理一下lazy标记。

  1 #include<cstdio>
  2 #include<cctype>
  3 #include<vector>
  4 inline int getint() {
  5     register char ch;
  6     while(!isdigit(ch=getchar()));
  7     register int x=ch^'0';
  8     while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
  9     return x;
 10 }
 11 const int N=300001;
 12 int a[N];
 13 std::vector<int> e[N];
 14 inline void add_edge(const int &u,const int &v) {
 15     e[u].push_back(v);
 16     e[v].push_back(u);
 17 }
 18 int n,dep[N],par[N],size[N],son[N],top[N],id[N],node[N],ans[N];
 19 void dfs1(const int &x) {
 20     size[x]=1;
 21     for(unsigned i=0;i<e[x].size();i++) {
 22         const int &y=e[x][i];
 23         if(y==par[x]) continue;
 24         par[y]=x;
 25         dep[y]=dep[x]+1;
 26         dfs1(y);
 27         size[x]+=size[y];
 28         if(size[y]>size[son[x]]) {
 29             son[x]=y;
 30         }
 31     }
 32 }
 33 void dfs2(const int &x) {
 34     id[x]=++id[0];
 35     node[id[x]]=x;
 36     if(x==son[par[x]]) {
 37         top[x]=top[par[x]];
 38     } else {
 39         top[x]=x;
 40     }
 41     if(son[x]) dfs2(son[x]);
 42     for(unsigned i=0;i<e[x].size();i++) {
 43         const int &y=e[x][i];
 44         if(y==par[x]||y==son[x]) continue;
 45         dfs2(y);
 46     }
 47 }
 48 class SegmentTree {
 49     #define _left <<1
 50     #define _right <<1|1
 51     private:
 52         int val[N<<2];
 53     public:
 54         void modify(const int &p,const int &b,const int &e,const int &l,const int &r,const int &x) {
 55             if(b==l&&e==r) {
 56                 val[p]+=x;
 57                 return;
 58             }
 59             const int mid=(b+e)>>1;
 60             if(l<=mid) modify(p _left,b,mid,l,std::min(mid,r),x);
 61             if(r>mid) modify(p _right,mid+1,e,std::max(mid+1,l),r,x);
 62         }
 63         void stat(const int &p,const int &b,const int &e) {
 64             if(b==e) {
 65                 ans[node[b]]=val[p];
 66                 return;
 67             }
 68             val[p _left]+=val[p];
 69             val[p _right]+=val[p];
 70             const int mid=(b+e)>>1;
 71             stat(p _left,b,mid);
 72             stat(p _right,mid+1,e);
 73         }
 74     #undef _left
 75     #undef _right
 76 };
 77 SegmentTree t;
 78 inline void modify(int u,int v) {
 79     t.modify(1,1,n,id[v],id[v],-1);
 80     while(top[u]!=top[v]) {
 81         if(dep[top[u]]<dep[top[v]]) std::swap(u,v);
 82         t.modify(1,1,n,id[top[u]],id[u],1);
 83         u=par[top[u]];
 84     }
 85     if(dep[u]<dep[v]) std::swap(u,v);
 86     t.modify(1,1,n,id[v],id[u],1);
 87 }
 88 int main() {
 89     n=getint();
 90     for(register int i=1;i<=n;i++) a[i]=getint();
 91     for(register int i=1;i<n;i++) {
 92         add_edge(getint(),getint());
 93     }
 94     dfs1(1);
 95     dfs2(1);
 96     for(register int i=1;i<n;i++) {
 97         modify(a[i],a[i+1]);
 98     }
 99     t.stat(1,1,n);
100     for(register int i=1;i<=n;i++) {
101         printf("%d
",ans[i]);
102     }
103     return 0;
104 }