題解 P3899 湖南集訓 談笑風生

2022-06-16 07:47:19 字數 1513 閱讀 7079

luogu智慧推薦給我搞的這個題啊,亦可賽艇!

題目連結

題目大意:和wallace談笑風生,給定一棵有根樹,多次詢問給定點\(p\)和限制\(k\),求有多少對有序三元組\((p,b,c)\)滿足\(p,b\)均為\(c\)的祖先且\(p,b\)間距離不超過\(k\)

主席樹,樹上差分

分析:首先我們分類討論一下

如果點\(b\)在點\(p\)上方時,有\(min(dep[p] - 1,k)\times(siz[p]-1)\),\(dep\)表示深度,\(siz\)表示子樹大小,乘法原理顯然

關鍵是當點\(b\)在點\(p\)子樹內是,對於一個確定的點\(b\),顯然點\(c\)可以選擇的數量就是\(siz[b]-1\)

問題變成了,給定一棵樹,每個點有一個點權,求一個點子樹內與它距離不超過\(k\)的點的權值之和

首先我們如果以深度為下標建一棵線段樹,假設我們知道一個點子樹的線段樹的話查詢就是區間求和問題,但是暴力計算時空複雜度均無法承受

我們考慮子樹的性質,如果求\(dfs\)序的話,一棵子樹內點的\(dfs\)序一定是連續的,因此我們可以用主席樹來計算,差分即可得到一個點子樹的線段樹

#include #include #include using namespace std;

const int maxn = 3e5 + 100;

typedef long long ll;

inline int read()

namespace sttree[maxnode];

int root[maxn],tot;

inline void pushup(int root)

inline void add(int last,int &root,int pos,int val,int l = 1,int r = 3e5)

int mid = (l + r) >> 1;

if(pos <= mid)tree[root].rs = tree[last].rs,add(tree[last].ls,tree[root].ls,pos,val,l,mid);

else tree[root].ls = tree[last].ls,add(tree[last].rs,tree[root].rs,pos,val,mid + 1,r);

pushup(root);

} inline ll query(int last,int root,int a,int b,int l = 1,int r = 3e5)

}using namespace st;

vectorg[maxn];

inline void addedge(int from,int to)

int dep[maxn],dfn[maxn],rnk[maxn],siz[maxn],dfs_tot,n,q;

inline void dfs(int u,int faz = -1)

}int main()

return 0;

}

洛谷P3899 湖南集訓 談笑風生 線段樹合併

題目連結 線段樹合併板子題,目前我看到兩種寫法,分別是這樣的。 前一種每次需要新建一個節點,空間是 o 4nlogn 後者不需要新建,空間是 o nlogn 面向資料算空間你懂得 ,但是需要離線,因為共用節點的緣故,之後的修改可能會修改到不需要修改的節點 好繞啊 這題就是把向上向下的貢獻分開算,然後...