Codeforces ラウンド #225 (ディビジョン 1)C (dfs+ライン セグメント ツリー)_html/css_WEB-ITnose

C. 伝播ツリー

テストごとの制限時間

2 秒

テストごとのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

Iahub は木がとても好きです多くの。最近、彼は繁殖木という興味深い木を発見しました。ツリーは、1 から n までの番号が付けられた n 個のノードで構成され、各ノード i は初期値 ai を持ちます。ツリーのルートはノード 1 です。

このツリーには特別なプロパティがあります。値 val がノード i の値に追加されると、値 -val がノード i のすべての子の値に追加されます。値 -val をノード i の子に追加すると、ノード i の子のすべての子にも -(-val) が追加されることに注意してください。仕組みをよりよく理解するには、説明例を見てください。

このツリーは 2 種類のクエリをサポートしています:

"1 x val" ? val はノード x の値に追加されます;

"2 x" ?ノード x の現在の値を出力します。

Iahub がツリーをよりよく理解できるようにするには、前述のタイプの m 個のクエリに答える必要があります。

入力

最初の行には 2 つの整数 n と m が含まれています(1?≤ ?n、?m?≤?200000)。 2 行目には、n 個の整数、a1、a2、...、an (1?≤?ai?≤?1000) が含まれています。次の n?1 行のそれぞれには、2 つの整数 vi と ui (1?≤?vi,?ui?≤?n) が含まれており、ノード vi と ui の間にエッジがあることを意味します。

次の m 行のそれぞれには、次の m 行が含まれます。上で説明した形式のクエリ。次の制約がすべてのクエリに適用されることが保証されています: 1?≤?x?≤?n,?1?≤?val?≤?1000.

出力

タイプ 2 の各クエリについて (値を出力します)ノード x の）クエリに対する回答を別の行に出力する必要があります。クエリは入力で指定された順序で回答する必要があります。

サンプル テスト

入力

5 51 2 1 1 21 21 32 42 51 2 31 1 22 12 22 4

出力

330

ノードの値は [ 1,?2,?1,?1,?2] が先頭にあります。

次に、値 3 がノード 2 に追加されます。それが伝播し、値 -3 がその子であるノード 4 とノード 5 に追加されます。その後、それはできませんこれ以上広めてください。したがって、ノードの値は [1,?5,?1,??-?2,??-?1] です。

次に、値 2 がノード 1 に追加されます。それが伝播し、値 -2 がノード 1 に追加されます。息子、ノード 2 とノード 3。ノード 2 から再び伝播し、その息子、ノード 4 とノード 5 に値 2 を追加します。ノード 3 には息子がないため、そこから伝播できません。ノードの値は [3,?3,??-?1,?0,?1] です。

ツリーに関するすべての定義は、次のリンクで確認できます: http://en.wikipedia.org /wiki/Tree_(graph_ Theory)

题：RT

思路：先dfs先序遍历、树形结构转線性

然后用两棵線段树、一个是奇数层の点、一は偶数層の点

1 x w より、如果x が奇数層の点、奇数点の線区树中、则x 被覆層区 (它のすべての子树の点)+ w，にもかかわらずカップ数点の回線セグメント树中，区间-w

用懒操作即完了可能