P4178 Tree

題意：

給定一棵 n 個節點的樹，每條邊有邊權，求出樹上兩點距離小于等于 k 的點對數量。

題解：

點分治的模板題是求等于K的路徑條數
本題是求小于等于K的路徑條數，我們只需要改變統計答案即可
原本統計答案是對一個路勁長度len，判斷K-len在之前的子樹中出現多少次，用f數組來記錄，直接查看f[k-len]等于多少即可
現在統計答案是對一個路徑長度len，判斷小于等于K-len的數在之前的子樹中出現多少次，統計區間數量，我們可以用樹狀數組來實現，對于每個len我們插入數組f[]其中，然后求1~K-len的區間查詢

代碼：

詳細看代碼

#include<bits/stdc++.h> #define MAXN 40005 #define MAXK 20005 using namespace std;int N,K;struct edge{int v,w;edge(int v=0, int w=0):v(v), w(w){} };vector<edge> adj[MAXN];// int fw[MAXK]; int lbt(int x){return x & (-x); } int getsum(int x){int ans = 0;for(;x>0;x-=lbt(x)){ans += fw[x];}return ans; }void change(int x, int dv){for(;x<=K;x+=lbt(x)){fw[x] += dv;} }// int sz[MAXN]; bool vis[MAXN]; int rt; void dfs_rt(int u, int fa, int tot){//O(tot)求根 sz[u] = 1;int v, n = 0;for(int k=0;k<adj[u].size();k++){v = adj[u][k].v;if(v==fa || vis[v]) continue;dfs_rt(v, u, tot);sz[u] += sz[v];n = max(n, sz[v]);}n = max(n, tot-sz[u]);if(n*2 <= tot) rt = u; }void dfs_sz(int u, int fa){//O(tot)求子樹sz[u] = 1;int v, n = 0;for(int k=0;k<adj[u].size();k++){v = adj[u][k].v;if(v==fa || vis[v]) continue;dfs_sz(v, u);sz[u] += sz[v];} }int d[MAXN], cnt = 0; void dfs_dis(int u, int fa, int dis){//O(tot)d[++cnt] = dis;//記錄距離 int v,w;for(int k=0;k<adj[u].size();k++){v = adj[u][k].v;w = adj[u][k].w;if(v==fa || vis[v]) continue;dfs_dis(v, u, dis + w);} }void dfs_clear(int u, int fa, int dis){//O(tot)清零 if(dis) change(dis, -1);int v,w;for(int k=0;k<adj[u].size();k++){v = adj[u][k].v;w = adj[u][k].w;if(v==fa || vis[v]) continue;dfs_clear(v, u, dis + w);} }int work(int u, int tot){ dfs_rt(u, 0, tot);u = rt;dfs_sz(u, 0);vis[u] = 1;int v,w;//solve/*求出每個點到根節點的距離，然后記錄到數組d然后對于d[i],查詢0~K-d[i]區間大小，用樹狀數組實現 如果d[i]<=K,那么d[i]本身也符合條件 將數組d插入到樹狀數組當以一個點為根的一輪結束時記得情況數組樹狀數組 */ int ans = 0;for(int k=0;k<adj[u].size();k++){v = adj[u][k].v;w = adj[u][k].w;if(vis[v]) continue;cnt = 0;dfs_dis(v, u, w);for(int i=1;i<=cnt;i++){if(d[i] <= K) ++ans;ans += getsum(max(0,K-d[i]));}for(int i=1;i<=cnt;i++){change(d[i], +1);}}dfs_clear(u,0,0);//手動清空 //for(int k=0;k<adj[u].size();k++){v = adj[u][k].v;//w = adj[u][k].w;if(vis[v]) continue;ans += work(v,sz[v]);} return ans; }int main(){cin>>N;int u,v,w;for(int i=1;i<N;i++){cin>>u>>v>>w;adj[u].push_back(edge(v,w));adj[v].push_back(edge(u,w));}cin>>K;cout<<work(1, N)<<endl;return 0; }

總結

以上是生活随笔為你收集整理的P4178 Tree的全部內容，希望文章能夠幫你解決所遇到的問題。

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