生活随笔
收集整理的這篇文章主要介紹了
Acwing 252. 树 点分治
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
傳送門
文章目錄
題意：
思路：
好久沒寫淀粉質了，心血來潮復習一下。
淀粉質通常用來統計路徑個數，將路徑分為子樹內的和子樹之間的。子樹內的遞歸處理，子樹間的存下信息來每次都處理即可，注意不要漏掉子樹到根節點的貢獻。
這個題要求不超過kkk的路徑有多少條，我們一個很容易想到的思路就是將每個子樹到偽重心的距離都存下來，每次與前面存下來的子樹信息算一下答案。
這個實現起來復雜度很高，每次計算答案需要遍歷之前的子樹，這樣就每一層的復雜度是O(n2)O(n^2)O(n2)級別的了，顯然不能接受。當然你可以使用一些黑科技維護一下，但是沒必要，我們有更好的算法。
考慮一個容斥，如果將所有路徑都存下來，排個序之后二分找答案，這樣算出來的答案可以發現不僅有兩個子樹之間的，還有子樹內部的，所以我們在每次遍歷完一個子樹的時候將答案減去即可。
由于每一層需要排序，復雜度O(nlognlogn)O(nlognlogn)O(nlognlogn)。
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#include<random>
#include<cassert>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].l+tr[u].r)>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;const int N
=10010,mod
=1e9+7,INF
=0x3f3f3f3f;
const double eps
=1e-6;int n
,k
;
vector
<PII
>v
[N
];
vector
<int>q
,qt
;
bool st
[N
];int get_size(int u
,int f
) {if(st
[u
]) return 0;int ans
=1;for(auto x
:v
[u
]) if(x
.X
!=f
) {ans
+=get_size(x
.X
,u
);}return ans
;
}int get_wc(int u
,int f
,int tot
,int &wc
) {if(st
[u
]) return 0;int sum
=1,mx
=0;for(auto x
:v
[u
]) {if(x
.X
==f
) continue;int now
=get_wc(x
.X
,u
,tot
,wc
);mx
=max(mx
,now
); sum
+=now
;}mx
=max(mx
,tot
-sum
);if(mx
<=tot
/2) wc
=u
;return sum
;
}void get_dis(int u
,int f
,int w
) {if(st
[u
]) return;q
.pb(w
);for(auto x
:v
[u
]) {if(x
.X
==f
) continue;get_dis(x
.X
,u
,w
+x
.Y
);}
}LL
calc(int u
) {if(st
[u
]) return 0;get_wc(u
,-1,get_size(u
,-1),u
);LL ans
=0; st
[u
]=true;for(auto x
:v
[u
]) {get_dis(x
.X
,-1,x
.Y
);sort(q
.begin(),q
.end());for(int i
=0;i
<q
.size();i
++) {int pos
=upper_bound(q
.begin(),q
.end(),k
-q
[i
])-q
.begin();ans
-=min(pos
,i
+1);qt
.pb(q
[i
]); ans
+=q
[i
]<=k
;}q
.clear();}sort(qt
.begin(),qt
.end());for(int i
=0;i
<qt
.size();i
++) {int pos
=upper_bound(qt
.begin(),qt
.end(),k
-qt
[i
])-qt
.begin(); ans
+=min(pos
,i
+1);}qt
.clear();for(auto x
:v
[u
]) ans
+=calc(x
.X
);return ans
;
}int main()
{
while(scanf("%d%d",&n
,&k
)&&(n
+k
)) {for(int i
=1;i
<=n
-1;i
++) {int a
,b
,w
; scanf("%d%d%d",&a
,&b
,&w
);v
[a
].pb({b
,w
}); v
[b
].pb({a
,w
});} printf("%lld\n",calc(0));for(int i
=0;i
<n
;i
++) v
[i
].clear(),st
[i
]=0;}return 0;
}
總結
以上是生活随笔為你收集整理的Acwing 252. 树 点分治的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
