개의 정점으로 이루어진 트리가 주어진다. 정점에는 의 번호가 붙어 있고, 처음에 번 정점에는 정수 가 적혀 있다.
다음 개의 질의를 순서대로 처리하여라. 질의를 처리하는 동안 그래프는 항상 트리이다.
0 : 현재 존재하는 간선 를 삭제하고, 간선 를 추가한다.1 : 로 바꾼다.입력은 다음과 같은 형식으로 주어진다.
각 2번 질의마다, 현재 트리에서 해당 경로 위 정점값의 합을 한 줄에 하나씩 출력한다.
처음 정점값은 이다.
첫 번째 출력은 경로 의 합 이다.
2 : 현재 트리에서 번 정점과 번 정점을 잇는 단순 경로 위의 모든 정점값의 합을 출력한다. 양 끝 정점도 포함한다.각 ()에 대해 처음 트리에는 번 정점과 번 정점을 잇는 간선이 있다.
0번 질의에서 이고, 질의 직전에 간선 가 존재한다. 간선 를 삭제하고 간선 를 추가한 뒤에도 그래프는 트리이다.1번 질의에서 이고 이다.2번 질의에서 이다.그 뒤 번 정점의 값이 이 된다. 두 번째 출력은 경로 의 합 이다.
간선 를 삭제하고 을 추가한 뒤, 세 번째 출력은 경로 의 합 이다.
간선 을 삭제하고 을 추가한 뒤, 마지막 출력은 경로 의 합 이다.