题目大意：
给你一棵树，要从编号为a[1]的节点走到编号为a[2]的节点再走到编号为a[3]的节点……一直走到编号为a[n]的节点。问每个节点最少访问多少次。
思路：
将其进行轻重链剖分，则从a[i]走到a[i+1]实际上就是在几段重链的节点上+1，于是就用线段树来维护一下即可。
代码：
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #define M 1200000 6 using namespace std; 7 8 int ans[M],to[M],head[M],next[M],vis[M],size[M],deep[M],id[M],top[M],sum[M],fa[M],a[M],cnt,dfn,n; 9 10 void add(int x,int y) 11 { 12 to[++cnt]=y; 13 next[cnt]=head[x]; 14 head[x]=cnt; 15 } 16 17 void dfs1(int x) 18 { 19 size[x]=vis[x]=1; 20 for (int i=head[x];i;i=next[i]) 21 if (!vis[to[i]]) 22 { 23 deep[to[i]]=deep[x]+1; 24 fa[to[i]]=x; 25 dfs1(to[i]); 26 size[x]+=size[to[i]]; 27 } 28 } 29 30 void dfs2(int x,int chain) 31 { 32 int k=0,i; 33 id[x]=++dfn; 34 top[x]=chain; 35 for (i=head[x];i;i=next[i]) 36 if (deep[to[i]]>deep[x] && size[to[i]]>size[k]) k=to[i]; 37 if (!k) return; 38 dfs2(k,chain); 39 for (i=head[x];i;i=next[i]) 40 if (deep[to[i]]>deep[x] && to[i]!=k) dfs2(to[i],to[i]); 41 } 42 43 void push_down(int cur) 44 { 45 sum[cur<<1]+=sum[cur]; 46 sum[cur<<1|1]+=sum[cur]; 47 sum[cur]=0; 48 } 49 50 void ADD(int L,int R,int l,int r,int cur) 51 { 52 if (l<=L && r>=R) 53 { 54 sum[cur]++; 55 return; 56 } 57 push_down(cur); 58 int mid=L+R>>1; 59 if (l>mid) ADD(mid+1,R,l,r,cur<<1|1); 60 else if (r<=mid) ADD(L,mid,l,r,cur<<1); 61 else ADD(L,mid,l,mid,cur<<1),ADD(mid+1,R,mid+1,r,cur<<1|1); 62 } 63 64 int ask(int l,int r,int x,int cur) 65 { 66 if (l==r) return sum[cur]; 67 push_down(cur); 68 int mid=l+r>>1; 69 if (x>mid) return sum[cur]+ask(mid+1,r,x,cur<<1|1); 70 else return sum[cur]+ask(l,mid,x,cur<<1); 71 } 72 73 void Add(int x,int y) 74 { 75 for (;top[x]!=top[y];x=fa[top[x]]) 76 { 77 if (deep[top[x]]<deep[top[y]]) swap(x,y); 78 ADD(1,n,id[top[x]],id[x],1); 79 } 80 if (deep[x]<deep[y]) swap(x,y); 81 ADD(1,n,id[y],id[x],1); 82 } 83 84 int main() 85 { 86 int i,x,y; 87 scanf("%d",&n); 88 for (i=1;i<=n;i++) scanf("%d",&a[i]); 89 for (i=1;i<n;i++) scanf("%d%d",&x,&y),add(x,y),add(y,x); 90 dfs1(1); 91 dfs2(1,1); 92 for (i=1;i<n;i++) Add(a[i],a[i+1]); 93 for (i=1;i<=n;i++) 94 { 95 ans[i]=-(i!=a[1]); 96 ans[i]+=ask(1,n,id[i],1); 97 } 98 for (i=1;i<=n;i++) printf("%d\n",ans[i]); 99 return 0; 100 }
转载于:https://www.cnblogs.com/HHshy/p/5733977.html
相关资源：JAVA上百实例源码以及开源项目