首页 > 代码库 > 【洛谷P3258】松鼠的新家
【洛谷P3258】松鼠的新家
很好的一道题
LCA+树上前缀和
sum数组是前缀和数组,
分类讨论一下,
1.访问到一个点p1,若下一个点p2需要往儿子下面找的话,那么lca就是这个点p1,则sum[p1]--; sum[p2]++;
2.访问到一个点p1,若下一个点p2需要往父亲上找的话,那么lca就是p2,则sum[f[p2][0]]--; sum[f[p1][0]]++
3.访问到一个点p1,若下一个点p2需要跨过p1,p2的lca的话,则sum[lca]--; sum[f[lca][0]]--; sum[p1]++; sum[p2]++;
需要注意的就是判重(有些地方会重复加)
1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 const int N=300010,p=20; 5 int n,size,head[N<<1],a[N]; 6 int nxt[N<<1],to[N<<1]; 7 int father[N][p+10],sum[N],cnt[N],deep[N]; 8 void swap(int &a,int &b){ 9 int tmp=a; 10 a=b; 11 b=tmp; 12 } 13 void uni(int x,int y){ 14 size++; 15 nxt[size]=head[x]; 16 head[x]=size; 17 to[size]=y; 18 } 19 void dfs(int fa,int x){ 20 for (int k=head[x];k;k=nxt[k]){ 21 int y=to[k]; 22 if (y==fa) 23 continue; 24 deep[y]=deep[x]+1; 25 father[y][0]=x; 26 dfs(x,y); 27 } 28 } 29 void pre(){ 30 for (int j=1;j<=p;j++) 31 for (int i=1;i<=n;i++) 32 father[i][j]=father[father[i][j-1]][j-1]; 33 } 34 int LCA(int x,int y){ 35 if (deep[x]<deep[y]) 36 swap(x,y); 37 int d=deep[x]-deep[y]; 38 for (int j=p;j>=0;j--) 39 if (d&(1<<j)) 40 x=father[x][j]; 41 if (x==y) 42 return x; 43 for (int j=p;j>=0;j--) 44 if (father[x][j]!=father[y][j]){ 45 x=father[x][j]; 46 y=father[y][j]; 47 } 48 return father[x][0]; 49 } 50 void Dfs(int fa,int x){ 51 if (!nxt[head[x]]&&x!=1){ 52 cnt[x]=sum[x]; 53 return; 54 } 55 for (int k=head[x];k;k=nxt[k]){ 56 int y=to[k]; 57 if (fa==y) 58 continue; 59 Dfs(x,y); 60 cnt[x]+=cnt[y]; 61 } 62 cnt[x]+=sum[x]; 63 } 64 int main(){ 65 int x,y; 66 size=0; 67 scanf("%d",&n); 68 for (int i=1;i<=n;i++) 69 scanf("%d",&a[i]); 70 for (int i=1;i<n;i++){ 71 scanf("%d %d",&x,&y); 72 uni(x,y); 73 uni(y,x); 74 } 75 deep[1]=1; 76 dfs(0,1); 77 pre(); 78 int lca=LCA(a[1],a[2]); 79 sum[a[1]]++; 80 sum[a[2]]++; 81 sum[lca]--; 82 sum[father[lca][0]]--; 83 for (int i=2;i<n;i++){ 84 x=a[i]; 85 y=a[i+1]; 86 int lca=LCA(x,y); 87 if (x==lca){//down 88 sum[x]--; 89 sum[y]++; 90 } 91 else if (y==lca){//up 92 sum[father[y][0]]--; 93 sum[father[x][0]]++; 94 } 95 else{ 96 sum[y]++; 97 sum[father[x][0]]++; 98 sum[lca]--; 99 sum[father[lca][0]]--; 100 } 101 } 102 Dfs(0,1); 103 cnt[a[n]]--; 104 for (int i=1;i<=n;i++) 105 printf("%d\n",cnt[i]); 106 return 0; 107 }
【洛谷P3258】松鼠的新家
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。