bzoj3631 松鼠的新家树链poi~分

填坑填坑……链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3631

题意：每走一遍一个节点就要增加一次计数器，最后到达终点不需增加，输出按顺序游历整棵树每个节点计数器的值。

就是裸的树链剖分……唯一的坑点

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cstring>
  5 using namespace std;
  6 const int maxn=300005;
  7 struct node
  8 {
  9     int from,to,next;
 10 }edge[maxn<<1];
 11 int head[maxn],tot;
 12 void addedge(int u,int v)
 13 {
 14     edge[++tot]=(node){u,v,head[u]};head[u]=tot;
 15 }
 16 int n,ord[maxn],top[maxn],dep[maxn],pos[maxn],id[maxn],cnt,son[maxn],siz[maxn],pa[maxn];
 17 void dfs1(int root,int fa,int deep)
 18 {
 19     son[root]=0;dep[root]=deep;siz[root]=1;
 20     for(int i=head[root];i;i=edge[i].next)
 21     {
 22         int v=edge[i].to;
 23         if(pa[root]!=v)
 24         {
 25             pa[v]=root;
 26             dfs1(v,root,deep+1);
 27             siz[root]+=siz[v];
 28             if(siz[v]>siz[son[root]])son[root]=v;
 29         }
 30     }
 31 }
 32 void dfs2(int root,int tp)
 33 {
 34     top[root]=tp;pos[++cnt]=root;id[root]=cnt;
 35     if(son[root])dfs2(son[root],tp);
 36     for(int i=head[root];i;i=edge[i].next)
 37     {
 38         int v=edge[i].to;
 39         if(v!=pa[root]&&v!=son[root])dfs2(v,v);
 40     }
 41 }
 42 #define mid ((l+r)>>1)
 43 #define lc root<<1
 44 #define rc root<<1|1
 45 #define lson lc,l,mid
 46 #define rson rc,mid+1,r
 47 int sm[maxn<<2],st[maxn<<2];
 48 void pushdown(int root,int l,int r)
 49 {
 50     if(st[root])
 51     {
 52         st[lc]+=st[root];st[rc]+=st[root];
 53         sm[lc]+=st[root]*(mid-l+1);sm[rc]+=st[root]*(r-mid);
 54         st[root]=0;
 55     }
 56 }
 57 void update(int root)
 58 {
 59     sm[root]=sm[lc]+sm[rc];
 60 }
 61 void modify(int root,int l,int r,int L,int R)
 62 {
 63     if(L<=l&&r<=R)
 64     {
 65         sm[root]+=r-l+1;st[root]++;
 66         return;
 67     }
 68     pushdown(root,l,r);
 69     if(L<=mid)modify(lson,L,R);if(R>mid)modify(rson,L,R);
 70     update(root);
 71 }
 72 void modify(int x,int y)
 73 {
 74     int fx=top[x],fy=top[y];
 75     while(fx!=fy)
 76     {
 77         if(dep[fx]<dep[fy])swap(x,y),swap(fx,fy);
 78         modify(1,1,n,id[fx],id[x]);
 79         x=pa[fx];fx=top[x];
 80     }
 81     if(dep[x]>dep[y])swap(x,y);
 82     modify(1,1,n,id[x],id[y]);
 83 }
 84 int query(int root,int l,int r,int pos)
 85 {
 86     if(l==r)return sm[root];
 87     pushdown(root,l,r);
 88     if(pos<=mid)return query(lson,pos);
 89     else return query(rson,pos);
 90 }
 91 int haha()
 92 {
 93     scanf("%d",&n);
 94     for(int i=1;i<=n;i++)scanf("%d",&ord[i]);
 95     for(int i=1;i<n;i++)
 96     {
 97         int x,y;scanf("%d%d",&x,&y);
 98         addedge(x,y);addedge(y,x);
 99     }
100     dfs1(1,-1,1);dfs2(1,1);
101     for(int i=1;i<n;i++)modify(ord[i],ord[i+1]);
102     for(int i=1;i<=n;i++)
103     {
104         int val=query(1,1,n,id[i]);
105         if(i!=ord[1])val--;
106         printf("%d
",val);
107     }
108 }
109 int sb=haha();
110 int main(){;}

bzoj3631

可能就是除了开头的那个点每个点最后结果都要$-1$s，因为中间那些点加了两次，最后那个点到达后不再计数。

bzoj3631 松鼠的新家 树链poi~分

bzoj3631 松鼠的新家树链poi~分