2783: [JLOI2012]樹 Time Limit: 1 Sec Memory Limit: 128 MB Submit: 279 Solved: 174 在這個問題中，給定一個值S和一棵樹。在樹的每個節點有一個正整數，問有多少條路徑的節點總和達到S。路徑中節點的深度必須是升序的。假設節點1是根節點，根的深度是0，它的兒子節點的深度為1。路徑不必一定從根節點開始。 Input 第一行是兩個整數N和S，其中N是樹的節點數。 第二行是N個正整數，第i個整數表示節點i的正整數。 接下來的N-1行每行是2個整數x和y，表示y是x的兒子。 Output 輸出路徑節點總和為S的路徑數量。 Sample Input 3 3 1 2 3 1 2 1 3 Sample Output 2 HINT 對於100%數據，N≤100000，所有權值以及S都不超過1000。 【分析】可以發現，如果一個點是K條可行序列的終點，那麼K<=1。因為一個點的父親及其祖先都是唯一的。那麼我們可以先根據這個性質對數的結點進行前綴和操作。然後枚舉每個點，二分尋找它的祖先，使得那一段之和是S。關鍵就是如何快速地求出某個點的上K個父親。 以前沒有寫過倍增LCA，於是就自己YY、類似於ST表的思想，我們用f[i][j]表示從第i個點開始上面2^j的父親的編號。預處理還是簡單的，類似於區間DP。但有些時候我要找非2的整次冪的父親，怎麼辦？（沒看過正規題解，我的效率很低，莫噴）我的想法是用lowbit去接近、比如是7，我先找2^0，變成6，再找2^1，變成4，再找2^2。 整體效率：O（N*LOG(N)^2） 【代碼】 [cpp] #include<cstdio> #include<cmath> #define lowbit(x) (x&-x) #define STEP 18 #define N 100005 using namespace std; struct arr{int go,next;}a[N]; int f[N][STEP],data[N],end[N],sum[N],deep[N],cnt,j,root,n,s,i,x,y,ans,p; inline void add(int u,int v){a[++cnt].go=v;a[cnt].next=end[u];end[u]=cnt;} inline void tree(int k) { sum[k]=sum[f[k][0]]+data[k]; deep[k]=deep[f[k][0]]+1; for (int i=end[k];i;i=a[i].next) { int go=a[i].go;tree(go); } } inline void init() { for (int l=1;l<STEP;l++) for (int i=1;i<=n;i++) f[i][l]=f[f[i][l-1]][l-1]; } inline int get(int now,int fa) { int k=deep[now]-fa; while (k) { int t=lowbit(k);now=f[now][int(log2(t))]; k-=t;if (now==0) return 0; } return now; } inline int erfen(int l,int r) { if (l==r) return get(i,l); int mid=(l+r)/2,now=get(i,mid); if (sum[i]-sum[f[now][0]]>s||now==0) return erfen(mid+1,r); return erfen(l,mid); } int main() { scanf("%d%d",&n,&s); for (i=1;i<=n;i++) scanf("%d",&data[i]); for (i=1;i<n;i++) { scanf("%d%d",&x,&y); add(x,y);f[y][0]=x; } for (i=1;i<=n;i++) if (f[i][0]==0) {root=i;break;} deep[root]=1;tree(root);init(); for (i=1;i<=n;i++) { if (data[i]==s) {ans++;continue;} if (i==root) continue; p=erfen(1,deep[i]-1); if (sum[i]-sum[f[p][0]]==s) ans++; } printf("%d",ans); return 0; }
