OpenMMをcondaを使わずに入れる

メモ書きとして。

下準備

brew install cmake
brew install doxygen
brew install swig

をしておく
openmmのzipをgithubからダウンロード
zipを解凍。
openmm<バージョン>/buildを作り、その中で ccmake -Wno-dev ../
python3の入っている場所を確認し、設定を行う -> [c]を押す
成功したら -> [g]
失敗したら気合で直す。

make
sudo make install
sudo make PythonInstall 

で多分入った。

seica's team practice 2019 No.1 (The 2018 Amman Collegiate Programming Contest)

codeforces.com

The 2018 Amman Collegiate Programming Contest

seica, mamumamu, m_99 でチーム練をしました。
チーム名は気まぐれです。
難易度的には簡単な方っぽい。

~~~~~~ 以下ネタバレ ~~~~~~

コンテストの動き

mamumamuがA、私がB、m_99がCを読みます。
BとCはやるだけだったので適当に通します*1。
Aに関しては奪う区間の片方をどこかの区間の端に合わせれば見る箇所はm箇所なのであとは実装...。
右端を合わせるか左端を合わせるかみたいな話が少々面倒臭いですができそうなのでmamumamu に実装を投げますが、難しいので様子を見つつ他の問題に手をつけます。

ここで順位表を見るとHIが解かれていたのでm_99と私でそれを通します*2
。

Aがバグったっぽい、適度にデバッグを見つつ次の問題へ。

次はFっぽいです。
出来るだけ小さいもので貪欲に置き換えれそうですが。私が「エラトステネスの篩」が言えなくなって壊れます。
誤読で2WA出すもAC*3。

Aがバグったっぽい、適度にデバッグを見つつ次の問題へ。

次に通されていたのがDE。
Dに関して、基本的に縦か横のみで構築したくなりますが、6*5のケースでお絵描きすると反例が。

<><><
><><>
<><><
><><>
<><><
><><>

ではなくて

^<><>
v^<><
>v^<>
<>v^<
><>v^
<><>v

こんな感じ。
この斜め横断を出来るだけ作れば良さそうということで投げるとAC、やったね。

Eはグリッドの端(？)にくる面(？)個数を数えればいいということでAC。

2問とも実装軽くっていい感じでした。

あまり解かれていないものの流石にAに注力します。
実装方針は大事ですね、頑張るとAが通ります。

Mを見ます。
LCAやるだけなことがわかったので書きます。

MLEします。

// typedef long long ll;
typedef int ll;

MLEします。

グローバルできるものをグローバルにおきます。

REします。
MLEします。

二次元vectorを一次元にします。

MLEします。

...。

テストケースごとにinit()で初期化するように書いていたのにinit()を呼んでいないことに気がつきます(!?!?)。

TLEします。

cinをscanfにします。

ACします、大事故。

Jです、上位ビットから固定していけばできそうなので実装をお願いすると少しバグるもAC。

Gわかりそうでわからないと言ってる間に終了。

感想

下らないミスが多すぎました、反省です。
話し合いは割と上手く言ってた気がする、多分。

*1:Q:Bに2WA付いていますね、なんでですか？ A:私が折り返し処理を間違えていたからです

*2:Q:IにWAが付いていますね、なんでですか？ A:私が答えを昇順にし忘れたからです

*3:exact whole number ってなんですか、紛らわしいのでdivisibleとだけ書いてください

ICPC 国内予選 2019 参加記

ICPC国内予選に参加しました。

今年で4回目、結構な数になってきました。

今年のチームは私とmamumamuとこーはいちゃん*1のチーム「seica on the border」ででました。

毎年チームメンバー変わってるんですよね、来年はどうかな？とりあえず全員どこかに行く予定はなさそうです(多分)。

コンテスト前

久しぶりに
家出たけど鍵かけたか心配になって戻る、しかしやっぱり鍵かかってた
をやってしまった…。

— seica (@seica_at_se) July 12, 2019

最近やってなかったのですが久しぶりに心配になってやってしまいました。

おかげでちょこっと遅刻、これによるタイムロスが10分とかなので問題は他のところにありそうです。

会場について準備を整えます。

毎年リハーサルから本番までの時間の使い方に困ってます、今年はこーはいちゃんに F - Colorful Tree を教えていたり、mamumamu
に「Aで詰まったら私しゃぶしゃぶ食べたい」とパワハラ(？)をしていたりしました。

コンテスト

予定としてはmamumamuがA、こーはいちゃんがB、私がC。その後みんなでD,Eという感じ。

ということでコンテスト開始。

mamumamuがAでWAを出します、パワハラは良くない、nとmが違っていたのにすぐ気がつきAC

こーはいちゃんがその間にBを詰められていたので実装を二人でやってもらって、その間に私はCの方を進めます。

C、「全部試してみれば良さそう」だと思い考察を終わらせ、Dを読みます。D、区間でいい感じにしたくなります。

Bが通ったとのでCの実装、一通り書き終わった段階で気がつきます「解いている問題違った。」

分銅は天秤のどちらにものせれるんですよね、片方にしかのせてませんでした。頭が真っ白になります。頭がぱっぱらぱー*2になってしまったので二人にヘルプを頼むと秒で正しい解法が帰ってきます。

「全部試せばいいじゃん」

それはそうなので実装します、少しバグりかけましたがAC。

さてD、(余計に一周させるものをデフォルトで必要な回数の少ないものから順に増やしていったのち)区間のdfsでいい感じにしたくなっている私はそれを書くとサンプルが通るので投げます -> WA

うまい判例が思いつかずに困ったのでチームで話し合いに入ります。

ちなみにこの時はDはそれでいけそうな気持ちになってたのでEを考えていてもらってました。

確証の持てない考察がずっと続きます。そもそも前の解法がどう違っているのかがわかりません。ずるずる引きずられていきます。

順位的にもこのままだと予選通過は怪しいので肝が冷え始めます。なにがちがうのー？？

ふと見ると、こーはいちゃんが私のやつが無理そうなのを聞いて

dp[i][j] = i個目を見ている、前はj週余計に回している

を考えていました。

遷移に詰まってたみたいですがdpの定義に関しては事象の網羅はできていそうな気(少なくとも余計に回す回数が一回とは限らないという面で考察が進んでいた)がしたので頭そっちに切り替わり、遷移を考えます。

考えると遷移が詰められたので実装すると違う値が出てきます、困った。この時点で残り時間が30分とかでさらに肝が冷えます。

とりあえずデバック、見にくいからと処理のサイズを変更(1111*1111でdpしていたのをn*nにした)して回すと正しい値が出てきました。

よくわからないけどそれっぽいから投げちゃえと投げたらAC、えーって言います*3(あとで配列外参照していたことに気がつく)

４完です、この時37位くらい、予選通過できそうなことに安堵します。

Eについては二人から頑張ればできそうと聞いていましたが、今から始めるには時間がないので厳しいねって言いながら順位表眺めたりFちょっと考えてみたりしました*4。

コンテストおしまい。

反省

私全然活躍できてませんね、困った。チームメイトには感謝です。

今回で2回目のチームでのコンテストだったんですが、話し合いがちょいちょい噛み合わない面とか立ち回りが良くないところ(これは私が基本的に指示してたので私の責任なんですが)がありました。不必要なタイムロスが色々とあったように思います(考察が間違っていたとかバグが埋まったとかそうゆうものは仕方ないとして)。

練習不足ですね、得意不得意の相性は良さそうでうまくできればもっとパフォーマンスが上がりそうなので頑張りたいところです。

個人としてはこれで４年連続アジア地区予選に参加できることになりました。嬉しい話です、楽しみたいと思います。

おまけ

その場の勢いで「seica on the border」なんて名前にしましたがアジア地区の時点で何かしらボーダーに乗せておかないとなっていってます(今はAtCoderのレートが黄色のボーダー付近、これをあと数ヶ月続けたくはないです)

*1:HNがわからないのでこーはいちゃんとします

*2:間抜けで阿呆であるさま。「ぱあ」を強めた語。(weblio辞書より)

*3:えー

*4:おいおい

AOJ 2378 SolveMe

最近記事書いてなかったので書きます。
雰囲気です(数式の書き方がわからない...)。

を満たす と の組み合わせを求める問題
まあ、まずこの定式化をちゃんとできるかみたいな話からありますが...。

基本的に も も全単射である必要があります。( のときはこれに限りません)
まあ、部屋1と部屋2から右耳に乗ると同じ部屋に行く、みたいなことがあったら困るし、いけない部屋あっても当然困るので。
変形させると

としました。
は によって適当に決められるので、ある変換の 乗がある変換の 2 乗で表せられるような組み合わせを考えることになります。

さて、この変換はいくつかのサイクルからなるので、それを元にDPを考えます。
とすると

:= について大きさ のサイクルまで考えた、 個決まっている時の組み合わせ

また、このDPを計算するために

:= サイズの写像を乗したとき全て大きさのサイクルになる組み合わせ
:= サイズの写像を乗したとき全て大きさのサイクルになる組み合わせ

を定義します

遷移は

みたいな感じ
あるサイクルの大きさを とするとそれを 乗したとき 個に分かれることを考えながらうまくcycleA、cycleBを計算します。
のときは が全単射である必要がないのでその分をかけてあげます。

頭壊れる。

#include <bits/stdc++.h>
  
using namespace std;
  
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007
  
typedef long long ll;
typedef pair<ll,ll> P;
  
const ll N_MAX = 1001;
  
ll dp[N_MAX][N_MAX];
ll cycle[2][N_MAX][N_MAX];
ll fact[N_MAX];
ll invfact[N_MAX];
ll factPow[N_MAX][N_MAX];
ll invfactPow[N_MAX][N_MAX];
ll comb[N_MAX][N_MAX];
  
//a^b % MOD
ll mod_pow(ll a,ll b){
    ll ret = 1;
    ll c = a;
    for(int i = 0;i <= 60;i++){
        if(b & (1LL << i))ret = (ret * c) % MOD;
        c = (c * c) % MOD;
    }
    return ret;
}
//ａをbで割る
ll mod_div(ll a,ll b){
    ll tmp = MOD - 2,c = b,ret = 1;
    while(tmp > 0){
        if(tmp & 1){
            ret *= c;ret %= MOD;
        }
        c *= c;c %= MOD;tmp >>= 1;
    }
    return a*ret%MOD;
}
  
void mod_add(ll &a, ll b){
    a += b;
    if(a >= MOD)a -= MOD;
}
  
ll gcd(ll a, ll b){
    return (b == 0 ? a : gcd(b, a % b));
}
  
void calComb() {
    REP(i, N_MAX){
        REP(j, i + 1){
            if(j == 0 || j == i){
                comb[i][j] = 1;
            }
            else {
                comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % MOD;
            }
        }
    }
}
  
void calFact() {
    fact[0] = 1;
    invfact[0] = 1;
    for(ll i = 0;i < N_MAX ;i++){
        if(i < N_MAX - 1) {
            fact[i+1] = fact[i] * (i + 1) % MOD;
            invfact[i+1] = mod_div(1, fact[i+1]);
        }
  
        factPow[i][0] = 1;
        invfactPow[i][0] = 1;
        for(int j = 1;j < N_MAX;j++){
            factPow[i][j] = factPow[i][j-1] * fact[i] % MOD;
            invfactPow[i][j] = invfactPow[i][j-1] * invfact[i] % MOD;
        }
    }
}
  
void calCycle(ll type, ll t) {
    for(int i = 0;i < N_MAX;i++){
        cycle[type][i][0] = 1;
    }
    for(ll i = 1;i < N_MAX;i++) {
        ll now = i / gcd(i, t);
        vector<ll> tmp(N_MAX);
        for(ll j = 0;i * j < N_MAX;j++){
            ll m_kake = invfactPow[i][j] * factPow[i-1][j] % MOD;
            for(ll k = 0;k + i * j < N_MAX;k++){
                ll kake = fact[k + i * j] * invfact[k] % MOD;
                kake = kake * m_kake % MOD;
                kake = kake * invfact[j] % MOD;
                mod_add(tmp[k + i * j], cycle[type][now][k] * kake % MOD);
            }
        }
  
        for(ll j = 0;j < N_MAX;j++){
            cycle[type][now][j] = tmp[j];
        }
    }
}
  
int main(){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
  
    ll n, x, y, z;cin >> n >> x >> y >> z;
    ll t = abs(x - y + z);
  
    calFact();
    calComb();
    calCycle(0, t);
    calCycle(1, 2);
  
    dp[0][0] = 1;
    for(ll i = 1;i <= n;i++){
        for(ll j = n;j >= 0;j--){
            for(ll k = 0;k * i <= j;k++){
                ll pre = j - k * i;
                ll kake = cycle[0][i][k * i] * cycle[1][i][k * i] % MOD;
                kake = kake * comb[j][k * i] % MOD;
                ll wari = fact[k * i] * invfactPow[i][k] % MOD;
                wari = wari * invfact[k] % MOD;
                wari = wari * factPow[i-1][k] % MOD;
                mod_add(dp[i][j], dp[i-1][pre] * mod_div(kake, wari) % MOD);
            }
        }
    }
  
    if(x == 0 && y == 0 && z == 0)cout << (dp[n][n] * invfact[n] % MOD)* mod_pow(n, n) % MOD << endl;
    else cout << dp[n][n] << endl;
  
    return 0;
}

AtCoderで黄色になりました

おおおおーーー！！！ pic.twitter.com/XAggqe7uEO

— seica (@seica_at_se) January 12, 2019

AtCoderのコンテスト初参加から2年と5ヵ月。
ようやく黄色になれました、わーい。
ということで記録も兼ねて色々書いていこうかと思います。
例のごとくポエムになると思うので好きな人は見てくださいなって感じで。

黄色になるまで

にやったことなんて「問題を解く」くらいなので、参考として情報を色々書いてみることにします。
指標の1つとして是非。

• 高校時代の数学の成績はセンターで193点、河合模試の偏差値は大体70ちょっとくらいとってました。*1
• 数学オリンピックは1回参加したことがあります、しっかり予選落ちしました。
• プログラミングは大学に入ってから始めました(ほぼ競プロ開始と同時期と考えてよいと思います)。
• 今までに解いた問題数はTopCoderが4問、CodeForcesが90問、AtCoderが861問、AOJが208問、yukicoderが6問で計1169問。*2
• AtCoderの詳細はこんな感じ。

AC詳細inProblems

AC詳細inScores(黄色)

黄色時点の精進グラフ

こんな感じでしょうか。
あ、最近Re:ステージ！にはまっています。皆さんもぜひ。

AtCoder Problems、AtCoder Scoresすごいですね。私はこうゆう開発はしない人なので尊敬します。

気を付けていること、コンテスト中に考えていることなどの雑記

ここからは完全にポエムです。
競プロについて普段考えていることをつらつら書いていきます。

精進について

問題演習をする際は基本的に長くても1時間程度しか考えません。というかそれ以上持ちません(えー)
自力で解けない問題についてその解法が簡単に理解できるとは限らないので、その前に時間を使いすぎるとめげやすいというのもあります(笑)
どちらかというと考えて解けなかった問題について、どう吸収するかに時間をかけています。
解法そのものだけでなく、その解法に至る動機などを自分なりに考えると印象に残ったり他の問題に応用しやすくなったりする気がします。
解説については、AtCoderの問題だと私的には解説放送が一番好きです、りんごさんすごい。
PDFについても日本語の解説を読んでわからなかったら英語の解説を読んでみるのもいいと思います、内容全然違ったりもします。

デバッグについて、コードの書き方について

まあ、よく言われていますが。
サークル活動をしてると良く思いますが、バグったときにいかに早く修正するかはかなり重要な気がします。
例えば私は基本的にprintデバッグしていますが、printデバッグをするといっても何処で何をどうゆう形で出力するかで得られる情報は全然変わります。
上手いデバッグ方法を自分なりに確立するのは大事だと思います。

また、そもそもバグらせなければそんなことしなくて済みますので、コードを書くときには自分がわかりやすい、綺麗で簡単なコードを書くように気を使っています。*3

モチベーションについて

強くなりたいとやっていてもなかなかモチベーションを保てなかったりします。

ということで精進仲間を大切にしています。
実力が離れすぎていない*4人とコンテストで競ったり、問題について話したりすることでモチベーションを保っています。
付き合ってくれている人には感謝。

知見？について

よく典型だとかメタ典型だとか定石(定跡)*5だとか言われるやつです、それ以外にも問題を解くにあたって何を考えるべきかなどについても知見としておきます。
ブログとかで問題ごとにきれいにまとめれればいいんですが私には向いていないようで、最近はスプレットシートにまとめていたりします。
そうゆう知見は言語化することで定着できたりする気がします。

少し列挙してみると

• まずは全探索できないか考えてみる、全探索できるならそれをする。
• 半分に分けたら全探索できないかも最初に考えておく
• まず図示する
• 構築についてはまず達成可能性を考える(極端な例について考えてみる)
• 簡単に実験できないか
• 与えられる問題についての値をを２値に分けると簡単にならないか->二分探索など
• 与えられた問題についてある値を固定したら簡単にならないか(また隠れたパラメーターはないか)->そのパラメータをずらすとどうなるか、二分探索できないか
• ゲームの問題について、最善の状態から相手の真似をすると良いことが多い
• あるものについて、考慮する順番を決めると考えやすくならないか(制約のきついものから考えると良かったりする。組み合わせならそのあと階乗を掛けるなどする)
• 実は考えなくてもよいものはないか
• たくさんの操作をして、条件を満たす場合の数を求める問題は期待値で考えてHOGE倍すると良い
• グリッドの問題について、2*2の正方形のうちある要素が奇数個あるものについて注目する
• 操作をデータ構造に見立てる
• 余事象を考える(さらにその部分集合を考える->包除原理)
• 事を独立に考えられないかを考える(2次元座標の問題を縦と横で分けられないかなど)
• etc

かなり雑に列挙しましたが、こうゆう知見がいい感じにまとまるとよさそうですね。
日本語ゆるふわ過ぎませんか？*6

終わりに

ここまで読んでくださった方、ありがとうございます。
突然ですが2週間前のツイートを見てみます。

今年の目標
atcoder 橙
就職先を決める
絵うまくなる

— seica (@seica_at_se) December 31, 2018

今年中に橙になるそうです、橙になった記事は少ないしなれたら書きたいと思います。
お楽しみに。

*1:競プロやってる人の平均はどのあたりなんですかね、ちょっと気になります

*2:まあ、問題数だけだとあまり参考にならない気がしますが

*3:バグる時はバグります。仕方ないね、人間だもの

*4:はずの

*5:私は囲碁をやっていたのでどちらかというと「定石」派

*6:仕方ないね、せいかちゃんだもの

AGC029 C - Lexicographic constraints

ICPCっぽさを感じるね。

問題

C - Lexicographic constraints

考察

二部探索をする、「K種類の文字で実現可能か」について考える。

愚直にやろうとすると10＾9桁考えなくてはいけなくなるのでRun Lengthといわれる(であろう)実装をする。

aaabbbabbccbbbb

を

a3b3a1b2c2b4

とかく奴です。
実際'a'は最下位のとき以外省略するみたいな書き方をしています。

コード

#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007

typedef long long ll;
typedef pair<ll,ll> P;

bool naoppy(vector<ll> &v, ll mid) {
	vector<P> now;
	now.EB(0,-1);
	REP(i,v.size()){
		if(now.back().FI < v[i]){
			now.EB(v[i],0);
		}
		else {
			if(mid <= 1)return false;
			while(now.back().FI > v[i])now.pop_back();
			if(now.back().FI < v[i])now.EB(v[i],0);
			int tmp = now.back().FI;
			int top = now.back().FI;
			while(now.back().FI == top && now.back().SE == mid - 1){
				top = now.back().FI - 1;
				now.pop_back();
			}
			if(now.back().FI != top)now.EB(top,0);
			now.back().SE++;
			if(now.back().FI != tmp)now.EB(tmp,0);
			if(now.front().SE > -1)return false;
		}
		//REP(i,now.size())cout << "(" << now[i].FI << "," << now[i].SE << ") ";cout << endl;
	}
	return true;
}

int main(){
	
	ll n;cin >> n;
	vector<ll> v(n);
	REP(i,n)cin >> v[i];
	
	ll l = 0;
	ll r = 222222;
	
	while(r - l > 1){
		ll mid = (l + r) / 2;
		if(naoppy(v,mid))r = mid;
		else l = mid;
	}
	
	cout << r << endl;
	
	return 0;
}

上のコードについて、入力が

10
2 2 3 3 3 2 2 2 1 2

で、K = 3の時を見てみると、コメントされたところは

(0,-1) (2,0)
(0,-1) (2,1)
(0,-1) (2,1) (3,0)
(0,-1) (2,1) (3,1)
(0,-1) (2,1) (3,2)
(0,-1) (2,2)
(0,-1) (1,1) (2,0)
(0,-1) (1,1) (2,1)
(0,-1) (1,2)
(0,-1) (1,2) (2,0)

と出力される。(a, b)はa番目の文字がbというもの、書いていない桁はb=0です。
文字に置き換えると

aa
ab
aba
abb
abc
ac
ba
bb
c
ca

という感じでK=3で達成可能とわかる。
この実装では0桁目が-1でなくなったら失敗となります。

おまけ

seicaさんのソースコードに変数名でnaoppyの登場を目指すぞ

— naoppy (@NaoppyJ) December 15, 2018

私は意地が悪いので変数名にはしません。

ACM-ICPC 2018 Asia Yokohama Regional J Colorful Tree

問題

https://onlinejudge.u-aizu.ac.jp/resources/icpcooc2018/J.pdf

木が与えられる(頂点数100000まで)、各点には色が塗られている。
次の２つのクエリを最大100000回行う

1. ある頂点の色を塗り替える。

1. ある色に塗られている頂点が全て含まれるような最小の部分木の辺の数を出力する。

考察

各色について頂点集合を持つとすると、
１つ目のクエリについてはある色の頂点集合からその点を除き、他の色の頂点集合に加えるクエリになる。

１つの色に注目したとして、どうやって部分木を数えようかと色々書いているとLCAでできそうなのがわかる。

上の写真において、例えば10と3に色が塗られていて、新しく11に色を塗るとするとこの色の答えは１増えることになるが、それを10と11のLCAと11との深さの差と見ることができる。

10と11に色が塗られていて、新しく13に色を塗ろうとすると答えが５増えることになるが、これは11と13のLCAと13との深さの差と、10と11のLCAと11と13のLCAとの深さの差の和と見ることができる。

上記のように考えると、木の番号をオイラーツアーで廻った順に振ると良いことがわかり。
各変更クエリについて頂点Aを付け足すときは

• Aの番号の前後２つ頂点とのLCAと自身の深さの差のうち小さいほう
• Aを付け足す前の頂点全体のLCAと付け加えた後の全体のLCAの深さの差

の２つを見ればよいことがわかる。

頂点を削除するときはこれと逆の操作をすればよい。計算量はO((n+m) log n)

#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007

typedef long long ll;
typedef pair<ll,ll> P;

struct UF{
	vector<int> par;
	vector<int> sz;
	UF(int n):par(n),sz(n) {
		for(int i = 0; i < n; i++){
			par[i] = i;sz[i] = 1;
		}
	}
	int find(int x) {
		if (par[x] == x) return x;
		else return par[x] = find(par[x]);
	}
	void unite(int x, int y) {
		x = find(x); y = find(y);
		if (x == y) return;
		par[x] = y;
		sz[x] += sz[y];
	}
	bool same(int x, int y) { return find(x) == find(y); }
	int size(int n){return sz[find(n)];}
};

struct LCA{
	vector<vector<pair<int,int> > > g;
	vector<vector<int> > parent;
	vector<int> depth;
	UF uf;
	int sz;
	vector<bool> inited;
		
	LCA(int n):g(n),parent(20,vector<int>(n)),
	inited(n,false),depth(n),uf(n){sz = n;}
	
	void add_edge(int u,int v,int w = 1){
		if(uf.same(u,v))return;
		g[v].PB(MP(u,w));
		g[u].PB(MP(v,w));
		uf.unite(v,u);
	}
		
	void dfs(int v,int p,int d){
		inited[v] = true;
		parent[0][v] = p;
		depth[v] = d;
		REP(i,g[v].size()){
			if(g[v][i].FI != p)dfs(g[v][i].FI,v,d+1);
		}
	}
	
	void init(){
		REP(i,sz)if(!inited[i])dfs(uf.find(i),-1,0);
		REP(k,19){
			REP(i,sz){
				if(parent[k][i] < 0)parent[k+1][i] = -1;
				else parent[k+1][i] = parent[k][parent[k][i]];
			}
		}
	}
	
	int ret_lca(int a,int b){
		
		if(!uf.same(a,b))return -1;
		
		if(depth[a] > depth[b])swap(a,b);
		REP(k,20){
			if((depth[b] - depth[a])>>k&1)b = parent[k][b];
		}
		if(a == b)return a;
		
		for(int k = 19;k >= 0;k--){
			if(parent[k][a] != parent[k][b])
			{
				a = parent[k][a];
				b = parent[k][b];
			}
		}
		return parent[0][a];
	}
	
};

vector<vector<int>> v(111111);
int mp[111111];
int color[111111];
LCA lca(111111);

struct seica {
	set<pair<int,int>> s;
	int ans = 0;
	int top = 0;
	void add(int a){
		if(s.size() != 0){
			int ret = INF; 
			auto now = s.lower_bound(MP(a, lca.depth[a]));
			if(now != s.end()){
				int tmp = lca.ret_lca(a, now->FI);
				ret = min(ret, abs(lca.depth[a] - lca.depth[tmp]));
				tmp = lca.ret_lca(top, tmp);
				ans += abs(lca.depth[top] - lca.depth[tmp]);
				top = tmp;
			}
			if(now != s.begin()){
				now--;
				int tmp = lca.ret_lca(a, now->FI);
				ret = min(ret, abs(lca.depth[a] - lca.depth[tmp]));
				tmp = lca.ret_lca(top, tmp);
				ans += abs(lca.depth[top] - lca.depth[tmp]);
				top = tmp;
			}
			if(ret == INF)ret = 0;
			ans += ret;
		}
		else{
			top = a;
		}
		s.insert(MP(a, lca.depth[a]));
	}
	
	void remove(int a) {
		auto now = s.lower_bound(MP(a, lca.depth[a]));
		int ret = INF;
		now++;
		if(now != s.end()){
			int tmp = lca.ret_lca(a, now->FI);
			ret = min(ret, abs(lca.depth[a] - lca.depth[tmp]));
		}
		now--;
		if(now != s.begin()){
			now--;
			int tmp = lca.ret_lca(a, now->FI);
			ret = min(ret, abs(lca.depth[a] - lca.depth[tmp]));
			now++;
		}
		if(ret == INF)ret = 0;
		ans -= ret;
		s.erase(now);
		if(s.size() > 0){
			int a = s.begin() -> FI;
			auto hoge = s.end();hoge--;
			int b = hoge -> FI;
			int tmp = lca.ret_lca(a, b);
			ans -= abs(lca.depth[tmp] - lca.depth[top]);
			top = tmp;
		}
	}
};

seica ixmel[111111];
int sum;
void dfs(int a,int pre){
	REP(i,v[a].size()){
		if(v[a][i] == pre)continue;
		mp[v[a][i]] = sum;sum++;
		lca.add_edge(mp[a], mp[v[a][i]]);
		dfs(v[a][i], a);
	}
}

int main(){
	
	int n;cin >> n;
	REP(i,n-1){
		int a, b;cin >> a >> b;
		a--;b--;
		v[a].PB(b);
		v[b].PB(a);

	}
	
	REP(i,n)cin >> color[i];
	mp[0] = sum;sum++;
	dfs(0, -1);
	lca.init();
	REP(i,n)ixmel[color[i]].add(mp[i]);
	
	int q;cin >> q;
	REP(i,q){
		char c;cin >> c;
		if(c == 'U'){
			int a, b;cin >> a >> b;a--;
			ixmel[color[a]].remove(mp[a]);
			ixmel[b].add(mp[a]);
			color[a] = b;
		}
		else{
			int a;cin >> a;
			if(ixmel[a].s.size())cout << ixmel[a].ans << endl;
			else cout << -1 << endl;
		}
	}
	
	return 0;
}

最近コードに自分や人の名前を使いがち。