https://atcoder.jp/contests/njpc2017/submissions/11405715

main.d

import std.stdio, std.string, std.algorithm, std.array, std.range, std.conv,
    std.typecons, std.math, std.container, std.format, std.numeric;

struct LinkCutNode
{
public:
    LinkCutNode* parent, left, right;

    void rotate()
    {
        LinkCutNode* c, p, pp;
        p = this.parent;
        pp = p.parent;

        if (p.left == &this)
        {
            c = this.right;
            p.left = c;
            this.right = p;
        }
        else
        {
            c = this.left;
            p.right = c;
            this.left = p;
        }

        if (pp && pp.left == p)
        {
            pp.left = &this;
        }
        if (pp && pp.right == p)
        {
            pp.right = &this;
        }
        this.parent = pp;
        p.parent = &this;
        if (c)
        {
            c.parent = p;
        }
    }

    int relation()
    {
        if (this.parent == null)
        {
            return 0;
        }
        if (this.parent.left == &this)
        {
            return 1;
        }
        if (this.parent.right == &this)
        {
            return -1;
        }

        return 0;
    }

    void splay()
    {
        // linkだけしてる場合 parent != null だが splay木の頂点には来ていることがあるので this.parent != nullと書くとバグる
        while (this.relation != 0)
        {
            if (this.parent.relation == 0)
            {
                this.rotate();
            }
            else if (this.relation == this.parent.relation)
            {
                this.parent.rotate();
                this.rotate();
            }
            else
            {
                this.rotate();
                this.rotate();
            }
        }
    }
}

void access(LinkCutNode* u)
{
    while (true)
    {
        u.splay();
        u.right = null;
        if (u.parent == null)
        {
            break;
        }

        u.parent.splay();
        u.parent.right = u;
    }
}

void link(LinkCutNode* u, LinkCutNode* v)
{
    u.parent = v;
}

void cut(LinkCutNode* u)
{
    access(u);
    u.left.parent = null;
    u.left = null;
}

LinkCutNode* root(LinkCutNode* u)
{
    access(u);
    auto now = u;
    while (now.left != null)
    {
        now = now.left;
    }
    now.splay();
    return now;
}

void main(string[] args)
{
    long n, q;
    readf("%d\n", &n);
    auto p = new long[](n + 1);
    auto c = new long[](n + 1);
    auto node = new LinkCutNode[](n + 1);
    foreach (i; 2 .. n + 1)
    {
        readf("%d\n", &p[i]);
    }
    foreach (i; 1 .. n + 1)
    {
        readf("%d\n", &c[i]);
    }
    foreach (i; 1 .. n + 1)
    {
        if (c[i] != c[p[i]])
        {
            link(&node[i], &node[p[i]]);
        }
    }

    readf("%d\n", &q);
    foreach (i; 0 .. q)
    {
        long cmd, u, v;
        readf("%d ", &cmd);

        if (cmd == 1)
        {
            readf("%d\n", &u);
            if (u == 1)
            {
                continue;
            }
            if (root(&node[u]) == root(&node[p[u]]))
            {
                cut(&node[u]);
            }
            else
            {
                link(&node[u], &node[p[u]]);
            }
        }
        else
        {
            readf("%d %d\n", &u, &v);
            if (root(&node[u]) == root(&node[v]))
            {
                writeln("YES");
            }
            else
            {
                writeln("NO");
            }
        }
    }
}