Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- using namespace __gnu_pbds;
- using namespace std;
- #define int long long
- #define mp make_pair
- #define pb push_back
- #pragma GCC optimize("Ofast")
- #pragma GCC optimize("unroll-loops")
- #pragma GCC target("avx2")
- constexpr int INF = (int)2e15;
- constexpr int N = (int)1e5 + 111;
- constexpr int md = (int)998244353;
- constexpr int mdPower = (int)1e9+7 - 1;
- constexpr double eps = 1e-7;
- typedef __int128 _uint;
- typedef long long ll;
- mt19937_64 rnd(time(nullptr));
- void add(int& a,int b){
- a += b; if(a >= md) a -= md;
- }
- void sub(int& a,int b){
- a -= b; while(a < 0) a += md;
- }
- void add(__int128& a,int b){
- a += b;
- }
- void sub(__int128& a,int b){
- a -= b;
- }
- int bpow(int a,int b){
- if(b == 0)
- return 1;
- if(b % 2 == 0){
- int t = bpow(a,b>>1);
- return 1ll*t*t%md;
- }
- return 1ll * a*bpow(a,b-1) % md;
- }
- int inv(int a){
- return bpow(a,md-2);
- }
- //int fac[N],invfac[N];
- //
- //void init(){
- // fac[0] = 1;
- // for(int i = 1; i < N; i++){
- // fac[i] = (fac[i-1] * i) % md;
- // }
- // invfac[N-1] = inv(fac[N-1]);
- // for(int i = N-2; i >= 0; i--){
- // invfac[i] = (invfac[i+1] * (i+1))%md;
- // }
- // return;
- //}
- //
- //int C(int n,int k){
- // if(k > n)
- // return 0;
- // return fac[n] * invfac[k] % md * invfac[n-k] % md;
- //}
- //
- //int A(int n,int k){
- // if(k > n)
- // return 0;
- // return fac[n] * invfac[n-k] % md;
- //
- vector<int> g[N];
- multiset<pair<int,int>> vals[N];
- bool isCentroid[N];
- int sz[N];
- int root[20][N];
- int prevCentroid[N];
- int go[N];
- void dfs1(int v,int pr = -1){
- sz[v] = 1;
- for(auto& to : g[v]){
- if(to == pr || isCentroid[to])
- continue;
- dfs1(to,v);
- sz[v] += sz[to];
- }
- return;
- }
- int dfs2(int v,int& n,int pr = -1){
- for(auto& to : g[v]){
- if(pr == to || sz[to] < n/2)
- continue;
- return dfs2(to,n,v);
- }
- return v;
- }
- vector<int> order;
- int tin[20][N],tout[20][N];
- int timer = {};
- int lvl[N];
- void dfs3(int v,int d,int pr = -1){
- order.pb(v);
- tin[d][v] = timer;
- for(auto& to : g[v]){
- if(to == pr || isCentroid[to])
- continue;
- dfs3(to,d,v);
- }
- order.pb(v);
- tout[d][v] = timer;
- return;
- }
- multiset<int> answer;
- bool upper(int a,int b,int d){
- return tin[d][a] <= tin[d][b] && tout[d][a] >= tout[d][b];
- }
- int CentroidDecomposition(int v,int d = 0){
- dfs1(v);
- int cur = dfs2(v);
- isCentroid[cur] = 1;
- dfs3(cur,d);
- lvl[cur] = d;
- for(auto& to : g[cur]){
- if(!isCentroid[to]){
- int p = CentroidDecomposition(to,d+1);
- prevCentroid[p] = v;
- go[p] = to;
- }
- }
- return cur;
- }
- int t[4*20*N];
- int w[4*20*N];
- void push(int v){
- t[v<<1] += w[v];
- t[v<<1|1] += w[v];
- w[v<<1] += w[v];
- w[v<<1|1] += w[v];
- w[v] = 0;
- return;
- }
- void upd(int v,int l,int r,int tl,int tr,int x){
- if(l > r || tl > tr)
- return;
- if(l == tl && r == tr){
- t[v] += x;
- w[v] += x;
- return;
- }
- int m = (l+r)>>1;
- push(v);
- upd(v<<1,l,m,tl,min(tr,m),x);
- upd(v<<1|1,m+1,r,max(m+1,tl),tr,x);
- t[v] = max(t[v<<1],t[v<<1|1]);
- return;
- }
- int get(int v,int l,int r,int tl,int tr){
- if(l > r || tl > tr)
- return 0;
- if(l == tl && r == tr)
- return t[v];
- int m = (l+r)>>1;
- push(v);
- return max(get(v<<1,l,m,tl,min(tr,m)),get(v<<1|1,m+1,r,max(m+1,tl),tr));
- }
- void updEdge(int v,int d,int a,int b,int delta){
- if(v == 0 || d < 0)
- return;
- if(upper(a,b,d))
- swap(a,b);
- upd(1,0,timer,tin[d][a],tout[d][a],delta);
- }
- void solve(){
- int n,q,w;
- cin >> n >> q >> w;
- for(int i = 1; i < n; i++){
- }
- return;
- }
- signed main(){
- ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
- int tests = 1;
- cin >> tests;
- for(int test = 1; test <= tests; test++){
- // cerr << "test = " << test << "\n";
- solve();
- }
- return 0;
- }
- /**
- **/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement