#include<bits/stdc++.h>
using namespace std ;
#define maxn 400009
#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define left id<<1
#define right id<<1|1
#define re exit(0);
#define _lower(v,x) lower_bound(v.begin(),v.end(),x)-v.begin()+1
int mod = 1e9+7 ;
const int INF = 1e9 ;
const int LOG = 18 ;
typedef vector<int> vi ;
typedef pair<int,int> pii ;
typedef vector<pii> vii ;
typedef vector<ll> vl ;
typedef pair<ll,ll> pll ;
typedef vector<pll> vll ;
void add ( int&a , int b ) { if ((a+=b) > mod ) a -= mod ; }
void sub ( int&a , int b ) { if ((a-=b) < 0 ) a += mod ; }
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
void rf ( )
{
freopen ("bai1.inp","r",stdin) ;
// freopen ("bai1.out","w",stdout) ;
}
int _pow ( int a , int n )
{
if ( n == 0 ) return 1 ;
int res = _pow ( a , n / 2 ) ;
if ( n % 2 ) return ( 1ll * res * res % mod * a % mod ) ;
else return ( 1ll * res * res % mod ) ;
}
int n ;
vi adjList [maxn] ;
int a [maxn] ;
int nq ;
struct shape {
int op , x , d , w ;
} q [maxn] ;
bool vis [maxn] ;
void update_near ( int u , int d , int w , int par = -1 )
{
a [u] = 1ll*a[u]*w%mod ;
if ( d == 0 ) return ;
for ( auto v : adjList [u] )
{
if ( v != par ) update_near (v,d-1,w,u) ;
}
}
void sub1 ()
{
for ( int rn = 1 ; rn <= nq ; rn ++ )
{
if ( q[rn].op == 1 )
{
int x = q [rn].x , d = q [rn].d , w = q [rn].w ;
update_near (x,d,w) ;
}
else cout << a [q[rn].x] << "\n" ;
}
}
bool check_sub2 ()
{
for ( int i = 1 ; i <= nq ; i ++ )
{
if ( q [i].op == 1 && q [i].d >= 2 ) return false ;
}
return true ;
}
vi vex [maxn] ;
int special [maxn] ;
int lazy_val [maxn] ;
void sub2 ()
{
for ( int i = 1 ; i <= n ; i ++ ) lazy_val [i] = 1 ;
int num = 0 ;
for ( int i = 1 ; i <= n ; i ++ )
{
if ( adjList [i].size () > 500 )
{
special [i] = true ;
}
}
for ( int i = 1 ; i <= n ; i ++ )
{
if ( special [i] == false )
{
for ( auto x : adjList [i] )
{
if ( special [x] == true ) vex [i] . pb (x) ;
}
}
}
for ( int rn = 1 ; rn <= nq ; rn ++ )
{
if ( q[rn].op == 1 )
{
int x = q [rn].x , d = q [rn].d , w = q [rn].w ;
if ( d == 0 )
{
a [x] = 1ll*a[x]*w%mod ;
continue ;
}
if ( special [x] == false ) update_near (x,d,w) ;
else lazy_val [x] = 1ll*lazy_val[x]*w%mod ;
}
else
{
int x = q [rn].x ;
int res = 1ll*a[x]*lazy_val[x]%mod ;
for ( auto v : vex [x] ) res = 1ll*res*lazy_val[v]%mod ;
cout << res << "\n" ;
}
}
}
signed main ( )
{
ios_base :: sync_with_stdio (0) ;
cin.tie(0) ; cout.tie(0) ;
rf () ;
cin >> n >> mod ;
for ( int i = 1 ; i < n ; i ++ )
{
int u , v ; cin >> u >> v ;
adjList [u] . pb (v) ;
adjList [v] . pb (u) ;
}
for ( int i = 1 ; i <= n ; i ++ ) cin >> a [i] ;
cin >> nq ;
for ( int i = 1 ; i <= nq ; i ++ )
{
cin >> q [i].op ;
if ( q[i].op == 1 )
{
cin >> q[i].x >> q[i].d >> q[i].w ;
}
else cin >> q[i].x ;
}
if ( n <= 1000 && nq <= 1000 ) sub1 () ;
else sub2 () ;
}
//-std=c++11
Compilation message
sprinkler.cpp: In function 'void sub2()':
sprinkler.cpp:94:6: warning: unused variable 'num' [-Wunused-variable]
94 | int num = 0 ;
| ^~~
sprinkler.cpp: In function 'void rf()':
sprinkler.cpp:32:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
32 | freopen ("bai1.inp","r",stdin) ;
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
22872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
22876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
22876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
22872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
22876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
22872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
