문제
1ドル$부터 $N$까지 번호가 매겨진 $N$개의 정점으로 이루어진 트리 $T$가 주어진다. 각 $i$번 정점은 정수 가중치 $A_i$를 가진다.
$T$의 연결 부분 집합 $S$는 $T$의 정점들의 공집합이 아닌 부분 집합으로, $S$에 속하는 두 정점 $a,ドル $b$에 대해 $S$에 속한 정점만을 사용하는 $a$에서 $b$로 가는 경로가 $T$에 존재한다.
다음 $Q$개의 쿼리를 처리해야 한다.
- $k$ $x$: $A_k$를 $x$로 바꾸고 $T$의 연결 부분 집합 $S$에 대한 $\sum_{i\in S}{A_i}$의 최댓값을 출력한다.
출력
$Q$개의 줄에 걸쳐 쿼리의 정답을 한 줄에 하나씩 출력한다.
제한
- 1ドル\leq N\leq 10^5$
- $-10^9\leq A_i\leq 10^9$ (1ドル\leq i\leq N$)
- 1ドル\leq u_i,v_i\leq N$ (1ドル\leq i\leq N-1$)
- 주어지는 그래프는 트리이다.
- 1ドル\leq Q\leq 10^5$
- 각 쿼리에 대해 1ドル\leq k\leq N$
- 각 쿼리에 대해 $-10^9\leq x\leq 10^9$
서브태스크
| 번호 | 배점 | 제한 | | 1 | 10 | $N, Q \leq 10^3$
|
| 2 | 20 | 각 정점의 차수는 3ドル$ 미만이다.
|
| 3 | 70 | 추가적인 제약 조건이 없다.
|
W3sicHJvYmxlbV9pZCI6IjMxODIwIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiVHJlZSBLYWRhbmUiLCJkZXNjcmlwdGlvbiI6IjxwPiQxJFx1YmQ4MFx1ZDEzMCAkTiRcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzljNCAkTiRcdWFjMWNcdWM3NTggXHVjODE1XHVjODEwXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWQyYjhcdWI5YWMgJFQkXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxICRpJFx1YmM4OCBcdWM4MTVcdWM4MTBcdWM3NDAgXHVjODE1XHVjMjE4IFx1YWMwMFx1YzkxMVx1Y2U1OCAkQV9pJFx1Yjk3YyBcdWFjMDBcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPiRUJFx1Yzc1OCA8c3Ryb25nPlx1YzVmMFx1YWNiMCBcdWJkODBcdWJkODQgXHVjOWQxXHVkNTY5PFwvc3Ryb25nPiAkUyRcdWIyOTQgJFQkXHVjNzU4IFx1YzgxNVx1YzgxMFx1YjRlNFx1Yzc1OCBcdWFjZjVcdWM5ZDFcdWQ1NjlcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YmQ4MFx1YmQ4NCBcdWM5ZDFcdWQ1NjlcdWM3M2NcdWI4NWMsICRTJFx1YzVkMCBcdWMxOGRcdWQ1NThcdWIyOTQgXHViNDUwIFx1YzgxNVx1YzgxMCAkYSQsICRiJFx1YzVkMCBcdWIzMDBcdWQ1NzQgJFMkXHVjNWQwIFx1YzE4ZFx1ZDU1YyBcdWM4MTVcdWM4MTBcdWI5Y2NcdWM3NDQgXHVjMGFjXHVjNmE5XHVkNTU4XHViMjk0ICRhJFx1YzVkMFx1YzExYyAkYiRcdWI4NWMgXHVhYzAwXHViMjk0IFx1YWNiZFx1Yjg1Y1x1YWMwMCAkVCRcdWM1ZDAgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgJFEkXHVhYzFjXHVjNzU4IFx1Y2ZmY1x1YjlhY1x1Yjk3YyBcdWNjOThcdWI5YWNcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPiRrJCAkeCQ6ICRBX2skXHViOTdjICR4JFx1Yjg1YyBcdWJjMTRcdWFmYjhcdWFjZTAgJFQkXHVjNzU4IDxzdHJvbmc+XHVjNWYwXHVhY2IwIFx1YmQ4MFx1YmQ4NCBcdWM5ZDFcdWQ1Njk8XC9zdHJvbmc+ICRTJFx1YzVkMCBcdWIzMDBcdWQ1NWMgJFxcc3VtX3tpXFxpbiBTfXtBX2l9JFx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4MTVcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM4MTVcdWMyMTggJE4kXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhYzAxIFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWFjMDBcdWM5MTFcdWNlNThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0ICROJFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggJEFfMSxBXzIsXFxkb3RzICxBX04kXHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgJE4tMSRcdWFjMWNcdWM3NTggXHVjOTA0IFx1YzkxMSAkaSRcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjQ1MCBcdWM4MTVcdWMyMTggJHVfaSRcdWM2NDAgJHZfaSRcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjRlNFx1Yzc0MCAkaSRcdWJjODhcdWM5ZjggXHVhYzA0XHVjMTIwXHVjNzU4IFx1YzU5MSBcdWIwNWQgXHVjODEwXHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMCBcdWNmZmNcdWI5YWNcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM4MTVcdWMyMTggJFEkXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjICRRJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YWMwMSBcdWM5MDRcdWM1ZDAgXHVhYzAxIFx1Y2ZmY1x1YjlhY1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHViNDUwIFx1YzgxNVx1YzIxOCAkayRcdWM2NDAgJHgkXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPiRRJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1Y2ZmY1x1YjlhY1x1Yzc1OCBcdWM4MTVcdWIyZjVcdWM3NDQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4kMVxcbGVxIE5cXGxlcSAxMF41JDxcL2xpPlxyXG5cdDxsaT4kLTEwXjlcXGxlcSBBX2lcXGxlcSAxMF45JCAoJDFcXGxlcSBpXFxsZXEgTiQpPFwvbGk+XHJcblx0PGxpPiQxXFxsZXEgdV9pLHZfaVxcbGVxIE4kICgkMVxcbGVxIGlcXGxlcSBOLTEkKTxcL2xpPlxyXG5cdDxsaT5cdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVhZGY4XHViNzk4XHVkNTA0XHViMjk0IFx1ZDJiOFx1YjlhY1x1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+JDFcXGxlcSBRXFxsZXEgMTBeNSQ8XC9saT5cclxuXHQ8bGk+XHVhYzAxIFx1Y2ZmY1x1YjlhY1x1YzVkMCBcdWIzMDBcdWQ1NzQgJDFcXGxlcSBrXFxsZXEgTiQ8XC9saT5cclxuXHQ8bGk+XHVhYzAxIFx1Y2ZmY1x1YjlhY1x1YzVkMCBcdWIzMDBcdWQ1NzQgJC0xMF45XFxsZXEgeFxcbGVxIDEwXjkkPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMSI6IjxwPiROLCBRIFxcbGVxIDEwXjMkPFwvcD5cclxuIiwic3VidGFzazIiOiI8cD5cdWFjMDEgXHVjODE1XHVjODEwXHVjNzU4IFx1Y2MyOFx1YzIxOFx1YjI5NCAkMyQgXHViYmY4XHViOWNjXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsInN1YnRhc2szIjoiPHA+XHVjZDk0XHVhYzAwXHVjODAxXHVjNzc4IFx1YzgxY1x1YzU3ZCBcdWM4NzBcdWFjNzRcdWM3NzQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjMxODIwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVHJlZSBLYWRhbmUiLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBhcmUgZ2l2ZW4gYSB0cmVlICRUJCB3aXRoICROJCB2ZXJ0aWNlcyBudW1iZXJlZCAkMSQgdG8gJE4kLiBFYWNoIHZlcnRleCAkaSQgaGFzIGFuIGludGVnZXIgd2VpZ2h0ICRBX2kkLjxcL3A+XHJcblxyXG48cD5BIDxzdHJvbmc+Y29ubmVjdGVkIHN1YnNldDxcL3N0cm9uZz4gJFMkIG9mICRUJCBpcyBhIG5vbmVtcHR5IHN1YnNldCBvZiB2ZXJ0aWNlcyBpbiAkVCQgc3VjaCB0aGF0LCBmb3IgYW55IHR3byB2ZXJ0aWNlcyAkYSQsICRiJCBpbiAkUyQsIHRoZXJlIGV4aXN0cyBhIHBhdGggYmV0d2VlbiAkYSQsICRiJCBpbiAkVCQgdGhhdCBvbmx5IHVzZXMgdGhlIHZlcnRpY2VzIGZyb20gJFMkLjxcL3A+XHJcblxyXG48cD5Zb3UgbmVlZCB0byBwZXJmb3JtIHRoZSBmb2xsb3dpbmcgJFEkIHF1ZXJpZXM6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+JGskICR4JDogY2hhbmdlICRBX2skIHRvICR4JCBhbmQgcHJpbnQgdGhlIG1heGltdW0gdmFsdWUgb2YgJFxcc3VtX3tpXFxpbiBTfXtBX2l9JCB3aGVyZSAkUyQgaXMgYSA8c3Ryb25nPmNvbm5lY3RlZCBzdWJzZXQ8XC9zdHJvbmc+IG9mICRUJC48XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciAkTiQgJm1kYXNoOyB0aGUgbnVtYmVyIG9mIHZlcnRpY2VzLjxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgJE4kIGludGVnZXJzICRBXzEsQV8yLFxcZG90cyAsQV9OJCBzZXBhcmF0ZWQgYnkgYSBzcGFjZSAmbWRhc2g7IHRoZSB3ZWlnaHRzIG9mIGVhY2ggdmVydGV4LjxcL3A+XHJcblxyXG48cD5UaGUgJGkkLXRoIG9mIHRoZSBuZXh0ICROLTEkIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VycyAkdV9pJCBhbmQgJHZfaSQgc2VwYXJhdGVkIGJ5IGEgc3BhY2UgJm1kYXNoOyB0aGUgZW5kcG9pbnRzIG9mIHRoZSAkaSQtdGggZWRnZS48XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyICRRJCAmbWRhc2g7IHRoZSBudW1iZXIgb2YgcXVlcmllcy48XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgbmV4dCAkUSQgbGluZXMgY29udGFpbnMgdHdvIGludGVnZXJzICRrJCBhbmQgJHgkIHNlcGFyYXRlZCBieSBhIHNwYWNlICZtZGFzaDsgYXJndW1lbnRzIG9mIGVhY2ggcXVlcnkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UHJpbnQgJFEkIGxpbmVzLiBJbiBlYWNoIGxpbmUsIHByaW50IHRoZSBhbnN3ZXIgdG8gZWFjaCBxdWVyeS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPiQxXFxsZXEgTlxcbGVxIDEwXjUkPFwvbGk+XHJcblx0PGxpPiQtMTBeOVxcbGVxIEFfaVxcbGVxIDEwXjkkICgkMVxcbGVxIGlcXGxlcSBOJCk8XC9saT5cclxuXHQ8bGk+JDFcXGxlcSB1X2ksdl9pXFxsZXEgTiQgKCQxXFxsZXEgaVxcbGVxIE4tMSQpPFwvbGk+XHJcblx0PGxpPlRoZSBnaXZlbiBncmFwaCBpcyBhIHRyZWUuPFwvbGk+XHJcblx0PGxpPiQxXFxsZXEgUVxcbGVxIDEwXjUkPFwvbGk+XHJcblx0PGxpPiQxXFxsZXEga1xcbGVxIE4kIGZvciBlYWNoIHF1ZXJ5PFwvbGk+XHJcblx0PGxpPiQtMTBeOVxcbGVxIHhcXGxlcSAxMF45JCBmb3IgZWFjaCBxdWVyeTxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD4kTiwgUSBcXGxlcSAxMF4zJDxcL3A+XHJcbiIsInN1YnRhc2syIjoiPHA+RWFjaCB2ZXJ0ZXggaGFzIGEgZGVncmVlIGxlc3MgdGhhbiAkMyQuPFwvcD5cclxuIiwic3VidGFzazMiOiI8cD5ObyBhZGRpdGlvbmFsIGNvbnN0cmFpbnRzLjxcL3A+XHJcbiJ9XQ==