#include <bits/stdc++.h>
using namespace std;
#define int long long
int dp[200001][41];
int lo[200001][41];
int P[200001],dep[200001];
int Pr[200001][41];
int cnt = 0,n,l;
map<int,int> mp[200001];
vector<int> adj[200001];
int h[200001],sz[200001];
int vis[200001];
map<pair<int,int>,int> getIndex;
int dfs(int i,int pr){
sz[i] = 1;
for(auto j:adj[i]){
if(j==pr||vis[j])continue;
sz[i]+=dfs(j,i);
}
return sz[i];
}
int getCen(int i,int pr,int ss){
for(auto j:adj[i]){
if(j==pr||vis[j])continue;
if(sz[j]*2>ss)return getCen(j,i,ss);
}
return i;
}
void lol(int i,int pr,int co,int de){
mp[de][i] = co;
for(auto j:adj[i]){
if(j==pr||vis[j])continue;
lol(j,i,co,de);
}
}
void centroid(int i,int pr){
int cen = getCen(i,i,dfs(i,i));
vis[cen] = 1;
P[cen] = pr;
for(auto j:adj[cen]){
if(vis[j])continue;
lol(j,cen,j,cen);
getIndex[{cen,j}] = cnt++;
}
for(auto j:adj[cen]){
if(vis[j])continue;
centroid(j,cen);
}
}
void init(int i,int pr){
Pr[i][0] = pr;
dep[i] = dep[pr]+1;
for(int j = 1;j<19;j++){
Pr[i][j] = Pr[Pr[i][j-1]][j-1];
}
for(auto j:adj[i]){
if(j==pr)continue;
init(j,i);
}
}
long long fast(long long a,long long b){
if(b==0)return 1;
long long h = fast(a,b/2);h*=h;h%=l;
if(b&1)return (h*a)%l;
else return h;
}
int lca(int a,int b){
int sum = dep[a]+dep[b];
if(dep[a]<dep[b])swap(a,b);
for(int j = 18;j>=0;j--){
if(dep[Pr[a][j]]>=dep[b])a = Pr[a][j];
}
if(a==b){
return sum-2*dep[a];
}
for(int j = 18;j>=0;j--){
if(Pr[a][j]!=Pr[b][j]){
a = Pr[a][j];
b = Pr[b][j];
}
}
return sum-2*dep[Pr[a][0]];
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
//freopen("input.txt","r",stdin);
//freopen("outout.txt","w",stdout);
cin>>n>>l;
for(int i = 0;i<n-1;i++){
int a,b;cin>>a>>b;
adj[a].push_back(b);
adj[b].push_back(a);
}
for(int i = 1;i<=n;i++){
cin>>h[i];
}
//cout<<"hhh"<<endl;
init(1,1);
//cout<<"hhh"<<endl;
centroid(1,-1);
for(int i = 1;i<=n;i++){
for(int j = 0;j<=40;j++)dp[i][j] = 1;
if(i<=cnt){
for(int j = 0;j<=40;j++)lo[i-1][j] = 1;
}
}
//cout<<"hhh"<<endl;
int q;cin>>q;
while(q--){
int ty;cin>>ty;
if(ty==1){
int x,d,v;
cin>>x>>d>>v;
int org = x;
for(int j = 0;j<=d;j++)dp[x][j]++;
while(P[x]!=-1){
x = P[x];
int w = mp[x][org];
int id = getIndex[{x,w}];
int le = lca(x,org);
if(le<=d){
for(int j = 0;j<=d-le;j++){
lo[id][j]*=v;lo[id][j]%=l;
dp[x][j]*=v;dp[x][j]%=l;
}
}
}
}else{
int x;cin>>x;
long long all = (h[x]*dp[x][0])%l;
int org = x;
while(P[x]!=-1){
x = P[x];
int w = mp[x][org];
int id = getIndex[{x,w}];
int le = lca(x,org);
all*=dp[x][le];all%=l;
all*=fast(lo[id][le],l-2);all%=l;
}
cout<<all<<endl;
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
24924 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
25040 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
24920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
24920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
24924 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
24924 KB |
Output is correct |
| 2 |
Execution timed out |
4051 ms |
445296 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
24924 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
25040 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
