結果
問題 | No.650 行列木クエリ |
ユーザー |
![]() |
提出日時 | 2018-10-11 18:10:08 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 185 ms / 2,000 ms |
コード長 | 4,575 bytes |
コンパイル時間 | 930 ms |
コンパイル使用メモリ | 95,976 KB |
実行使用メモリ | 45,712 KB |
最終ジャッジ日時 | 2024-10-12 17:38:27 |
合計ジャッジ時間 | 3,307 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 10 |
ソースコード
#include <cstdio>#include <cstring>#include <string>#include <iostream>#include <cmath>#include <bitset>#include <vector>#include <map>#include <set>#include <queue>#include <deque>#include <algorithm>#include <unordered_map>using namespace std;typedef long long int ll;typedef pair<ll, ll> P;typedef pair<int, int> Pi;typedef pair<P, P> PP;const ll MOD=1e9+7;int n;vector<Pi> g[100000];int e[100000];int sz[100000];bool used[100000];Pi p[100000];void dfs(int x){sz[x]=1;used[x]=1;for(auto pr:g[x]){int y=pr.first;if(used[y]) continue;p[y]=Pi(x, pr.second);dfs(y);sz[x]+=sz[y];}}int num[100000];int nume[100000];int ind[100000];vector<int> v[100000];Pi nump[100000];int ct;void dfs2(int x){int mx=0, y0=-1;for(auto pr:g[x]){int y=pr.first;if(y==p[x].first) continue;if(mx<sz[y]){mx=sz[y];y0=y;}}if(y0==-1) return;for(auto pr:g[x]){int y=pr.first;if(y==p[x].first) continue;if(y==y0){num[y]=num[x];v[num[x]].push_back(pr.second);}else{ct++;num[y]=ct;nump[num[y]]=Pi(x, pr.second);}}for(auto pr:g[x]){int y=pr.first;if(y!=p[x].first) dfs2(y);}}void indcalc(){fill(ind, ind+n-1, -1);for(int i=0; i<=ct; i++){for(int j=0; j<v[i].size(); j++){ind[v[i][j]]=j;nume[v[i][j]]=i;}}}vector<ll> x[100000][2][2];int m[100000];void init(){for(int i=0; i<=ct; i++){if(v[i].empty()) continue;m[i]=1;while(m[i]<v[i].size()) m[i]*=2;for(int j=0; j<2*m[i]-1; j++){x[i][0][0].push_back(1);x[i][1][1].push_back(1);x[i][0][1].push_back(0);x[i][1][0].push_back(0);}}}void update(int e, ll x00, ll x01, ll x10, ll x11){int k=m[nume[e]]-1+ind[e];int i0=nume[e];x[i0][0][0][k]=x00;x[i0][0][1][k]=x01;x[i0][1][0][k]=x10;x[i0][1][1][k]=x11;while(k>0){k=(k-1)/2;for(int s=0; s<2; s++){for(int t=0; t<2; t++){x[i0][s][t][k]=0;for(int u=0; u<2; u++){x[i0][s][t][k]+=(x[i0][s][u][2*k+1]*x[i0][u][t][2*k+2]);x[i0][s][t][k]%=MOD;}}}}}void matmul(ll x1[2][2], ll x2[2][2], ll ans[2][2]){for(int s=0; s<2; s++){for(int t=0; t<2; t++){ans[s][t]=0;for(int u=0; u<2; u++){ans[s][t]+=(x1[s][u]*x2[u][t]);ans[s][t]%=MOD;}}}}void find(int i0, int a, int b, int k, int l, int r, ll ans[2][2]){if(v[i0].empty() || r<=a || b<=l){ans[0][0]=1, ans[1][1]=1, ans[0][1]=0, ans[1][0]=0; return;}if(a<=l && r<=b){for(int s=0; s<2; s++){for(int t=0; t<2; t++){ans[s][t]=x[i0][s][t][k];}}return;}ll ansl[2][2], ansr[2][2];find(i0, a, b, 2*k+1, l, (l+r)/2, ansl);find(i0, a, b, 2*k+2, (l+r)/2, r, ansr);matmul(ansl, ansr, ans);}int main(){cin>>n;for(int i=0; i<n-1; i++){int a, b;cin>>a>>b;g[a].push_back(Pi(b, i));g[b].push_back(Pi(a, i));}ll x0[100000][2][2];for(int i=0; i<n-1; i++){for(int s=0; s<2; s++){for(int t=0; t<2; t++){if(s!=t) x0[i][s][t]=0;else x0[i][s][t]=1;}}}dfs(0);dfs2(0);indcalc();int q;cin>>q;init();for(int i=0; i<q; i++){char c; cin>>c;if(c=='x'){int e;cin>>e;cin>>x0[e][0][0]>>x0[e][0][1]>>x0[e][1][0]>>x0[e][1][1];if(ind[e]>=0) update(e, x0[e][0][0], x0[e][0][1], x0[e][1][0], x0[e][1][1]);}else{int v1, v2;cin>>v1>>v2;ll ans[2][2];if(num[v1]==num[v2]){int i1, i2;i2=ind[p[v2].second]+1;if(v1==0 || num[p[v1].first]!=num[v1]) i1=0;else i1=ind[p[v1].second]+1;find(num[v2], i1, i2, 0, 0, m[num[v2]], ans);cout<<ans[0][0]<<" "<<ans[0][1]<<" "<<ans[1][0]<<" "<<ans[1][1]<<endl;}else{int i1, i2, i3;i2=ind[p[v2].second]+1;if(v1==0 || num[p[v1].first]!=num[v1]) i1=0;else i1=ind[p[v1].second]+1;find(num[v2], 0, i2, 0, 0, m[num[v2]], ans);int n0=num[v2];while(1){ll ans1[2][2], ans2[2][2];matmul(x0[nump[n0].second], ans, ans1);for(int s=0; s<2; s++){for(int t=0; t<2; t++){ans[s][t]=ans1[s][t];}}int v3=nump[n0].first;n0=num[v3];if(v3==0 || num[p[v3].first]!=num[v3]) i3=0;else i3=ind[p[v3].second]+1;if(num[v1]==n0) break;find(n0, 0, i3, 0, 0, m[n0], ans2);matmul(ans2, ans, ans1);for(int s=0; s<2; s++){for(int t=0; t<2; t++){ans[s][t]=ans1[s][t];}}}ll ans1[2][2], ans0[2][2];find(num[v1], i1, i3, 0, 0, m[num[v1]], ans1);matmul(ans1, ans, ans0);cout<<ans0[0][0]<<" "<<ans0[0][1]<<" "<<ans0[1][0]<<" "<<ans0[1][1]<<endl;}}}return 0;}