개의 정점으로 이루어진 트리가 있다. 정점에는 부터 까지 번호가 매겨져 있으며, 정점 의 초기 가중치는 이다.
아래의 쿼리를 수행하는 프로그램을 작성하라.
1 r x v: 트리의 루트를 로 정했을 때, 의 서브트리에 속한 모든 정점의 가중치에 를 더한다.2 x y v: 에서 까지의 경로에 속한 모든 정점의 가중치에 를 더한다.3 x y z: 이 쿼리에서 와 는 인접한 두 정점으로 주어진다. 와 사이의 간선을 삭제한다. 그러면 트리가 두 개의 연결 성분으로 나뉜다. 와 중 와 다른 연결 성분에 속한 정점을 와 간선으로 연결한다.첫째 줄에 정점의 수 과 쿼리의 수 이 주어진다.
다음 개 줄에는 트리의 간선마다 두 정점 번호 , 가 주어진다.
다음 개 줄에는 정점 부터 정점 까지의 초기 가중치 이 순서대로 한 줄에 하나씩 주어진다.
번과 번 쿼리의 결과를 쿼리가 주어진 순서대로 각각 한 줄에 출력한다.
모든 쿼리를 처리한 뒤, 마지막으로 모든 정점의 가중치 합을 출력한다.
첫 번째 쿼리에서 모든 노드의 가중치가 만큼 증가한다. 두 번째 쿼리에서 번 노드의 가중치인 이 출력된다. 세 번째 쿼리에서 번 노드의 가중치가 만큼 증가한다. 마지막으로 두 가중치의 합인 를 출력해야 한다.
4 x y: 에서 까지의 경로에 놓인 정점들의 가중치를 경로 순서에 따라 뒤집는다. 즉, 경로를 라고 할 때, 각 의 새 가중치는 쿼리 직전의 의 가중치가 된다. 정점의 연결 관계는 바뀌지 않는다.5 r x: 트리의 루트를 로 정했을 때, 의 서브트리에 속한 모든 정점의 가중치 합을 출력한다.6 x y: 에서 까지의 경로에 속한 모든 정점의 가중치 합을 출력한다.다음 개 줄에는 앞에서 설명한 형식의 쿼리가 주어진다.