题目大意：给定一棵无根树和一个序列，在这个序列上依次遍历，求每个点的访问次数(最后一个点的访问次数要-1)
树链剖分的裸题……考场上我还是一个弱渣，啥也不会，暴力得了50分，剩下两道题爆零了。。。而且30W深搜爆栈，人生第一次手写了系统栈。。
回来因为这题的原因去学了树链剖分 结果没学明白 每条重链单独开了一棵线段树 常数大的要死
高一时写的代码。。。还是别看了，拿去对拍可以，阅读性欠佳
#include<stdio.h>#include<stdlib.h>#include<string.h>#define M 300100#define min(x,y) x<y?x:ytypedef struct abcd{int xx,mark,l,r;abcd*ls,*rs;} abcd;abcd*tree[M];typedef struct abcde{int to;abcde*next;} abcde;abcde*head[M];void add(int x,int y){abcde*temp=(abcde*)malloc(sizeof(abcde));temp->to=y;temp->next=head[x];head[x]=temp;}void swap(int &x,int &y){int z=x;x=y;y=z;}int fa[M],siz[M],dpt[M],son[M],top[M],a[M],ans;void Build_tree(abcd*p,int l,int r){int mid=l+r>>1;p->l=l;p->r=r;p->xx=p->mark=0;p->ls=p->rs=NULL;if(l==r)return ;p->ls=(abcd*)malloc(sizeof(abcd));p->rs=(abcd*)malloc(sizeof(abcd));Build_tree(p->ls,l,mid);Build_tree(p->rs,mid+1,r);}void Up_load(abcd*p,int x,int y){int mid=p->l+p->r>>1;if(p->l==x&&p->r==y){p->xx+=p->r-p->l+1;p->mark++;return ;}if(y<=mid)Up_load(p->ls,x,y);else if(x>mid)Up_load(p->rs,x,y);else Up_load(p->ls,x,mid),Up_load(p->rs,mid+1,y);p->xx+=y-x+1;}int search(abcd*p,int x){int mid=p->l+p->r>>1;if(p->l==x&&p->r==x)return p->xx;p->ls->xx+=p->mark*(p->ls->r-p->ls->l+1);p->rs->xx+=p->mark*(p->rs->r-p->rs->l+1);p->ls->mark+=p->mark;p->rs->mark+=p->mark;p->mark=0;if(x<=mid)return search(p->ls,x);return search(p->rs,x);}int q[M],r,h;int maxsiz[M];void bfs(){abcde*temp;int x;q[++h]=1;while(r!=h){r++;x=q[r];dpt[x]=dpt[fa[x]]+1;siz[x]=1;for(temp=head[x];temp;temp=temp->next){if(temp->to==fa[x])continue;fa[temp->to]=x;q[++h]=temp->to;}}for(;r>=2;r–){x=q[r];siz[fa[x]]+=siz[x];if(siz[x]>maxsiz[fa[x]])maxsiz[fa[x]]=siz[x],son[fa[x]]=x;}for(r=1;r<=h;r++){x=q[r];if (son[fa[x]]!=x)top[x]=x,tree[x]=(abcd*)malloc(sizeof(abcd));else top[x]=top[fa[x]];if(son[x]==0)Build_tree(tree[top[x]],1,dpt[x]-dpt[top[x]]+1);}}int n;int main(){int i,x,y,f1,f2;scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&a[i]);for(i=1;i<n;i++)scanf("%d%d",&x,&y),add(x,y),add(y,x);bfs();for(i=1;i<n;i++){x=a[i];y=a[i+1];f1=top[x];f2=top[y];while(f1!=f2){if(dpt[f1]<dpt[f2])swap(x,y),swap(f1,f2);Up_load(tree[f1],1,dpt[x]-dpt[f1]+1);x=fa[f1];f1=top[x];}if(dpt[x]<dpt[y])swap(x,y);Up_load(tree[f1],dpt[y]-dpt[f1]+1,dpt[x]-dpt[f1]+1);}for(i=1;i<=n;i++)printf("%d\n",search(tree[top[i]],dpt[i]-dpt[top[i]]+1)-1+(i==a[1]));}
后来经过讨论其实这题LCA就能过。。。每次移动时在起始点和终点各打一个start标记，在LCA和LCA的父节点处各上打一个end标记，，然后深搜，start标记一直上传，遇到end标记就停止，最后再处理一下就行
我写的是TarjanLCA 这样询问深搜一遍处理 时间复杂度O(n)
#include<stdio.h>#include<stdlib.h>#include<string.h>#define M 300100struct abcd{int to,next;}table[M<<2];int head[M],query[M],tot;void add(int x,int y){table[++tot].to=y;table[tot].next=head[x];head[x]=tot;}void qadd(int x,int y){table[++tot].to=y;table[tot].next=query[x];query[x]=tot;}int fa[M],f[M],a[M],v[M];int start[M],end[M];int n;int find(int x){if(!f[x]||f[x]==x)return f[x]=x;return f[x]=find(f[x]);}void Tarjan(int x){int i;for(i=head[x];i;i=table[i].next)if(table[i].to!=fa[x])fa[table[i].to]=x,Tarjan(table[i].to),f[table[i].to]=x;v[x]=1;for(i=query[x];i;i=table[i].next)if(v[table[i].to])end[ fa[ find(table[i].to) ] ]++,end[ find(table[i].to) ]++;start[x]-=end[x];start[fa[x]]+=start[x];}int main(){int i,x,y;scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d",&a[i]);if(i^1){qadd(a[i],a[i-1]);qadd(a[i-1],a[i]);start[ a[i] ]++;start[ a[i-1] ]++;}}for(i=1;i<n;i++)scanf("%d%d",&x,&y),add(x,y),add(y,x);Tarjan(1);for(i=1;i<=n;i++)printf("%d\n", start[i] – (i!=a[1]) );}
在人生的大海中，我们虽然不能把握风的大小，却可以调整帆的方向。
