문제에서 주어지는 그래프는 함수형 그래프입니다.

함수형 그래프의 특징 중 하나는, 각 연결 요소마다 사이클이 정확히 하나씩 있으며, 그 사이클을 노드 하나로 생각하면 해당 노드가 트리의 루트가 된다는 것입니다.

따라서, 링크 컷 트리를 적용한 뒤, 사이클을 적절히 관리해주면 문제를 해결할 수 있습니다.

조금 더 자세히 설명하자면, 두 노드를 이어야 하는데 사이클이 형성될 경우, 링크 컷 트리 상에서는 잇지 않는 대신에 그 노드에 이어져 있어야 하는 노드 번호를 저장해주면 됩니다.

그러면 1, 3번 쿼리를 잘 처리해줄 수 있습니다.

2번 쿼리는 그냥 해 주면 됩니다.

아래는 C++ 코드입니다. (링크 컷 트리는 생략)

struct T {
    ptr p = null; // 이어져 있었어야 할 노드
    long long val = 0, sum = 0;
};

struct Node;
Node M[222222];

int main() {
    int n, q; cin >> n >> q;

    for(int i = 1; i <= n; i++) {
        int t; cin >> t;
        if(connected(t, i)) M[i].val.p = t;
        else link_(t, i);
    }

    for(int i = 1; i <= n; i++) {
        long long t; cin >> t;
        update(i, [&](ptr nd) { M[nd].val.val = t; });
    }

    while(q--) {
        long long t, i, j, x;
        cin >> t;
        if(t == 1) {
            cin >> i >> j;
            ptr rt = root(i), lf = M[rt].val.p, nx = lca(i, lf);
            if(nx == i) {
                M[rt].val.p = null;
                if(rt != lf && rt != nx)
                    cut(nx), link_(lf, rt);
            } else cut(i);

            if(connected(i, j)) M[i].val.p = j;
            else link_(j, i);
        } else if(t == 2) {
            cin >> i >> x;
            update(i, [&](ptr nd) { M[nd].val.val = x; });
        } else {
            cin >> x;
            ptr rt = root(x), lf = M[rt].val.p, nx = lca(x, lf);
            long long ans = -M[nx].val.val;
            path(rt, x, [&](ptr nd) { ans += M[nd].val.sum; });
            path(nx, lf, [&](ptr nd) { ans += M[nd].val.sum; });
            cout << ans << '\\n';
        }
    }
}