E - Through Path

これは好きなタイプの問題でした。かなり。

問題

頂点の木が与えられる。以下のクエリを処理したのち、各頂点の情報を出力せよ。

のとき : 頂点 から辺をたどって頂点 を通らずに到達できるような全ての頂点 に対して、をに書き換える。

のとき : 頂点 から辺をたどって頂点 を通らずに到達できるような全ての頂点 に対して、をに書き換える。

解法

クエリ毎に木を舐めていると当然間に合わない。各クエリを高速に処理するか、工夫して最後にうまく答えるかどちらかを考えてみる。今回は後者になる。LCAも解けそうだけど、今回は使いません（ライブラリ持ってないし…）

クエリには２種類あるがどちらもほとんど同じなので、以下では次のクエリを例として考える。

頂点 から辺をたどって頂点 を通らずに到達できるような全ての頂点 に対して、をに書き換える。

木の性質から、任意の二頂点の最短パスは一意に定まる。これを踏まえてクエリについて考えてみる。
から辺をたどって頂点を通らずに到達できるような頂点とは、直観的には、から見てと同じ側にある頂点、つまり、となる頂点の集合としたとき、となるような頂点集合である。この頂点にだけ値を追加すればよい。どうやって値を追加していくは最後に答えるとして、もう少し詳細を見てみよう。

上記の考察から、クエリ毎に値が変化する頂点の集合が二つに分かれることに気づく。さらに、その分け方は、適当な頂点を根とした木の距離を計算しておけば楽に導出できる。
この部分も少し補足しておこう、を満たすとき、つまり、根から見たときがより深いとき、　となる頂点がとなる。言い換えると、値が追加される頂点の集合は
逆にとなるとき、値が追加される集合()は、と、から親方向にたどってまでに到達するまでに存在する頂点であることがわかる。今回は隣接する頂点なので、値が追加される集合はだけ。

最後に値を追加する方法を考えよう。今までの考察から、どのクエリであっても、根から距離を基準として、その頂点の親と子供を見ればよいことがわかる。発想を変えてみて、クエリによって値を追加するとき、とりあえずすべての頂点に値を追加して、対象外の頂点だけに値を引いてみることを考えよう。

言い換えると、値を追加するとき、全体に追加するのであれば根に、木の子供に追加するなら親に値を追加すればよい。これと同じように、値を引くとき、負の値を親に追加すればよい。クエリをすべて処理した後、一度だけ深さ優先探索を行えば、整合性が取れた木が完成する。遅延評価っぽい戦略が見えると、比較的楽に取り組める。

提出

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>

using namespace std;
using Int  = long long;

void dfs(vector<vector<int>>&edge, vector<Int>&d, int v, int pv = -1)
{
    for(auto& nv : edge[v])
    {
        if(nv == pv)continue;
        d[nv] = d[v] + 1;
        dfs(edge,d,nv,v);
    }
    
    return;
}

void flush(vector<vector<int>>&edge, vector<Int>&d, vector<Int>&c, int v, int pv = -1)
{
    for(auto& nv : edge[v])
    {
        if( nv == pv) continue;
        c[nv] += c[v];
        flush(edge,d,c,nv,v);
    }
  return;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
  
    int N; cin >> N;
    vector<vector<int>>edge(N);
    vector<pair<int,int>>input;
    
    for(int i = 0; i + 1 < N; ++i)
    {
        int a,b;
        cin >> a >> b;
        --a; --b;
        edge[a].push_back(b);
        edge[b].push_back(a);
        input.emplace_back(a,b);
    }
    
    vector<Int>c(N,0LL);
    vector<Int>d(N,0LL);
    
    dfs(edge,d,0);
    
    int Q; cin >> Q;

    while( Q --> 0)
    {
        int t, e, x;
        cin >> t >> e >> x;

        --e;
        
        int pls, mns;
        
        if( t == 1)
        {
            pls = input[e].first;
            mns = input[e].second;
        }
        else
        {
            mns = input[e].first;
            pls = input[e].second;
        }
        
        if(d[pls] > d[mns])
        {
            c[pls] += x;
        }
        else
        {
            c[mns] -= x;
            c[0] += x;
        }
    }
    
    flush(edge,d,c,0);
    
    for(auto e : c)
        cout <<  e << endl;
    
}