https://atcoder.jp/contests/njpc2017/tasks/njpc2017_h

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;

    /// thisがparentの親になるように部分木をを回す
    void rotate()
    {
        LinkCutNode* c, p, pp;
        p = this.parent;
        pp = this.parent.parent;

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

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

        if (c != null)
        {
            c.parent = p;
        }
    }

    /// this が parentから見てどの位置にいるかを表せるようにしておくと便利
    int relation()
    {
        if (this.parent == null)
        {
            return 0;
        }
        if (this.parent.left == &this)
        {
            return 1;
        }
        if (this.parent.right == &this)
        {
            return -1;
        }
        return 0;
    }

    /// rotateを繰り返しながら this が木全体の根になるまで回す
    /// 親とのrelation、親と親の親とのrelationによって操作が変わる
    void splay()
    {
        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();
            }
        }
    }
}

/// treeを根から辿ってvまで辿るpathをつくる
/// pathが存在する == 同じsplay木の上にいる
void access(LinkCutNode* v)
{
    // vは根と同じsplay木の上にあるかも知れないし、根を指しているだけの別のsplay木（non Preferredなnodeで繋がっている木）の上にあるかも知れない
    // それが何回層あるかは不明なので何回でもやる
    while (true)
    {
        // 1. vをその木の中でのrootに持ってくる
        v.splay();

        // 2. vの右辺はvまで辿るには不要なので切り捨てる
        v.right = null;

        // vがrootと同じsplay木にいた
        if (v.parent == null)
        {
            break;
        }

        // 3. 親に認知してもらう
        // 親を根に持ってきて右辺はいらないので切り捨てて成り代わる
        v.parent.splay();
        v.parent.right = v;
    }
}

/// uをvにくっつける。ただしこれはSplay Treeとして指しているというよりはポインタなので、親からは認知されない
void link(LinkCutNode* u, LinkCutNode* v)
{
    u.parent = v;
}

/// uを親と切り離す
void cut(LinkCutNode* u)
{
    // Non Preferred な nodeを切り離しても何にもならないのでちゃんと認知してもらってから別れる
    // （よくわからないのでごまかした）
    u.access();
    u.left.parent = null;
    u.left = null;
}

/// 頂点uを上に辿り続けて根を返す
LinkCutNode* root(LinkCutNode* u)
{
    u.access();
    LinkCutNode* now = u;

    // 根はSplay木の左端
    while (now.left != null)
    {
        now = now.left;
    }
    now.splay();
    return now;
}

void main(string[] args)
{
    long n;
    readf("%d\n", &n);
    auto parents = new long[](n + 1);
    auto colors = new long[](n + 1);
    auto nodes = new LinkCutNode[](n + 1);
    foreach (i; 2 .. n + 1)
    {
        readf("%d\n", &parents[i]);
    }
    foreach (i; 1 .. n + 1)
    {
        readf("%d\n", &colors[i]);
    }

    // 親との経路が利用可能ならLinkする
    // これによって利用可能な経路でのみ繋がったSplay木がいくつかできる
    foreach (i; 2 .. n + 1)
    {
        if (colors[i] != colors[parents[i]])
        {
            link(&nodes[i], &nodes[parents[i]]);
        }
    }

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

            if (u == 1)
            {
                continue;
            }

            // 部分木の色すべてを反転してもそれらの関係はからわず、部分木の根とその親との関係だけが変わる
            if (root(&nodes[u]) == root(&nodes[parents[u]]))
            {
                // 経路は利用不可能になったので切り離す
                cut(&nodes[u]);
            }
            else
            {
                // 経路が繋がったのでLinkする
                link(&nodes[u], &nodes[parents[u]]);
            }
        }
        if (cmd == 2)
        {
            readf("%d %d\n", &u, &v);
            // 利用可能な経路のみで繋がっているので、同じ根を持つ要素全てにたどり着ける
            if (root(&nodes[u]) == root(&nodes[v]))
            {
                writeln("YES");
            }
            else
            {
                writeln("NO");
            }
        }
    }
}