Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[問題案] Dynamic Tree Vertex Add Subtree Sum(dynamic_tree_vertex_add_subtree_sum) #229

Closed
niuez opened this issue Dec 29, 2019 · 3 comments
Closed

Comments

@niuez
Copy link
Contributor

@niuez niuez commented Dec 29, 2019

問題ID: dynamic_tree_vertex_add_subtree_sum
問題名: Dynamic Tree Vertex Add Subtree Sum

問題概要

木が与えられる

(クエリの形は暫定)

  • link/cut 0 u v w x: 辺(u, v)を削除し, 辺(w, x)を作成
  • add 2 v x: 頂点vに重みxを加える
  • sum 3 r v: rを根としたときの頂点vの部分木

入力

N Q
a_0 a_1 ... a_{N - 1}
u_0 v_0
u_1 v_1
:
u_{N - 2} v_{N - 2}
Query0
Query1
:
Query_{Q - 1}

出力

制約

sumのクエリをどうするかですね. 根を最初に固定してもいいですが, どうしましょう?

@niuez niuez changed the title [問題案] Dynamic Tree Vertex Add Subtree Sum(dynamic_tree_vertex_add_Subtree_sum) [問題案] Dynamic Tree Vertex Add Subtree Sum(dynamic_tree_vertex_add_subtree_sum) Dec 29, 2019
@yosupo06

This comment has been minimized.

Copy link
Owner

@yosupo06 yosupo06 commented Dec 29, 2019

提案ありがとうございます!

sumのクエリをどうするかですね. 根を最初に固定してもいいですが, どうしましょう?

  1. 根を固定、常にiの親はiより小さい(親配列p_iをいじる感じ), evert不要
  2. link cutは好き放題にやるが、部分木のクエリの根だけ最初に決める
  3. 部分木のクエリごとに親を決める

があると思います。私の感想としては1はEuler Tour Treeとか考えると役に立つと思います、3は一番直感的な設定だと思います、2はあんまり利点がわからないです

ということで、3推し、つまり今↑に書いてある物推しです(1は役に立つけど結構特殊な設定だと思うので)

次に部分木の与え方ですが、

  1. (r, v) : 根と頂点を与える
  2. (p=parent(v), v) : 親と頂点を与える、つまり辺を与える

の2種類があると思います。個人的には2の方が好きかなと思ってます なぜなら1だとクエリ -> 部分木が単射でないからです。

@niuez

This comment has been minimized.

Copy link
Contributor Author

@niuez niuez commented Dec 29, 2019

単射の性質に気が付きませんでした. すごいです.

(p=parent(v), v) : 親と頂点を与える、つまり辺を与える

sumのクエリ形式はこれに賛成です. 「辺(p, v)について頂点pを親としたときの頂点vの部分木の重みの総和」という形で良いですか?

@yosupo06

This comment has been minimized.

Copy link
Owner

@yosupo06 yosupo06 commented Dec 29, 2019

はい!それでOKです もう少し言うと入力が2 p v2 v pかと言うのがあるんですが、どっちが自然かは謎(というより大して変わらない?)です 私としては2 v pを推しておきます

@yosupo06 yosupo06 added this to 作業待ち in 問題リスト Dec 29, 2019
@yosupo06 yosupo06 closed this Dec 29, 2019
問題リスト automation moved this from 作業待ち to 作成済み Dec 29, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
問題リスト
  
作成済み
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
2 participants
You can’t perform that action at this time.