容易發現是樹剖裸題。

然后毒瘤選手AKC表示好像可以用樹上差分+LCA做。

就這樣。水題。

誒那你咋沒秒切。

媽也看錯樣例，然后畫錯圖，接著就是理解錯題目，最后R成傻逼之時發現我ST表開數組的順序錯了。。。

廢物。

#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std;struct node {int x,y,next; }a[610000];int len,last[310000]; void ins(int x,int y) {len++;a[len].x=x;a[len].y=y;a[len].next=last[x];last[x]=len; }int Bin[30],f[310000][30]; int dep[310000]; void dfs(int x) {for(int i=1;i<=25;i++)if(dep[x]>=Bin[i])f[x][i]=f[f[x][i-1]][i-1];for(int k=last[x];k;k=a[k].next){int y=a[k].y;if(y!=f[x][0]){f[y][0]=x;dep[y]=dep[x]+1;dfs(y);}} } int LCA(int x,int y) {if(dep[x]<dep[y])swap(x,y);for(int i=25;i>=0;i--)if(dep[x]-dep[y]>=Bin[i])x=f[x][i];if(x==y)return x;for(int i=25;i>=0;i--)if(f[x][i]!=f[y][i]&&dep[x]>=Bin[i]) x=f[x][i], y=f[y][i];return f[x][0]; }//------LCA---------int ch[310000]; int tmp[310000]; void update(int x) {for(int k=last[x];k;k=a[k].next){int y=a[k].y;if(y!=f[x][0]){update(y);tmp[x]+=tmp[y];}} } int main() {int n,x,y;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&ch[i]);len=0;memset(last,0,sizeof(last));for(int i=1;i<n;i++){scanf("%d%d",&x,&y);ins(x,y);ins(y,x);}//----sc---- Bin[0]=1;for(int i=1;i<=25;i++)Bin[i]=Bin[i-1]*2;dep[1]=1;f[1][0]=0;dfs(1);for(int i=1;i<=n-1;i++){tmp[ch[i]]++;tmp[ch[i+1]]++;int lca=LCA(ch[i],ch[i+1]);tmp[lca]--;if(f[lca][0]!=0)tmp[f[lca][0]]--;}update(1);tmp[ch[1]]++;for(int i=1;i<=n;i++)printf("%d\n",tmp[i]-1);return 0; }

?

轉載于:https://www.cnblogs.com/AKCqhzdy/p/8562302.html

總結

以上是生活随笔為你收集整理的bzoj3631: [JLOI2014]松鼠的新家的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。