P3899 湖南集訓 談笑風生

2022-09-22 20:02:42 字數 1335 閱讀 2890

p3899 [湖南集訓]談笑風生

這題定義詭異,似乎對於一對 \(x, y\) 如果 \(y\) 是 \(x\) 在範圍 \(k\) 以內的兒子,那麼 \(x\) 既和它彼此彼此,又高明到不知道**去了

然後你思考一下,分兩部分:

\(x\) 是 \(y\) 的祖先。

\(y\) 是 \(x\) 的祖先。

容易發現,當你在 \(x\) 的時候.

第一部分 \(sum_1 = \min(dep_x - 1, k) \cdot (siz_x-1)\)。

第二部分 \(sum_2 = \displaystyle \sum_ siz_v\)。

第二部分顯然很線段樹合併,第一部分 \(o(1)\) 算。

#include #include #include #include #include using namespace std;

typedef long long ll;

const ll maxn = 3e5+10;

struct que

que(ll _k, ll _id)

};struct nod t[maxn * 30];

ll n, m, ans[maxn], siz[maxn], rt[maxn], tot;

vector g[maxn];

vector q[maxn];

ll ask(ll, ll, ll, ll, ll);

void dfs(ll, ll);

void dfs2(ll, ll, ll);

void ins(ll&, ll, ll, ll, ll);

ll mer(ll, ll);

int main()

for (ll i = 1, p, k; i <= m; i++)

dfs(1, 0);

dfs2(1, 0, 1);

for (ll i = 1; i <= m; i++)

printf("%lld\n", ans[i]);

return 0;

}void dfs(ll n, ll ff)

}void dfs2(ll n, ll ff, ll dep)

for (unsigned int i = 0; i < q[n].size(); i++)

}void ins(ll &node, ll l, ll r, ll pos, ll val)

ll ask(ll node, ll l, ll r, ll a, ll b)

ll mer(ll x, ll y)

題解 P3899 湖南集訓 談笑風生

luogu智慧推薦給我搞的這個題啊,亦可賽艇! 題目連結 題目大意 和wallace談笑風生,給定一棵有根樹,多次詢問給定點 p 和限制 k ,求有多少對有序三元組 p b c 滿足 p b 均為 c 的祖先且 p b 間距離不超過 k 主席樹,樹上差分 分析 首先我們分類討論一下 如果點 b 在點...

洛谷P3899 談笑風生

題目大意 給定一棵 n 個節點的有根樹,1 號節點為根節點,現給出 q 個詢問,每次詢問距離 u 號節點不超過 k 的節點 b,c 為 a 與 b 的後代,求這樣的三元組有多少個。 題解 學會了線段樹合併。 由於之前對線段樹合併理解的不深刻,導致狂 wa 不止qaq。 需要統計 sum operat...

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

設 t 為一棵有根樹,我們做如下的定義 設 a 和 b 為 t 中的兩個不同節點。如果 a 是 b 的祖先,那麼稱 a 比 b 不知道高明到 去了 。 設 a 和 b 為 t 中的兩個不同節點。如果 a 與 b 在樹上的距離不超過某個給定常數 x,那麼稱 a 與 b 談笑風生 。 給定一棵 n 個節...