Author : Dipu Kumar Mohanto
CSE, Batch - 6
BRUR.
Problem Statement : 100589A. Queries on the Tree
Source : Codeforces Gym
Category : Graph Theory
Algorithm : Squart Fragmented Tree / Block Tree
Verdict : Accepted
#include "bits/stdc++.h"
using namespace std;
#define FI freopen("in.txt", "r", stdin)
#define FO freopen("out.txt", "w", stdout)
#define FAST ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define FOR(i, n) for (int i = 1; i <= n; i++)
#define For(i, n) for (int i = 0; i < n; i++)
#define ROF(i, n) for (int i = n; i >= 1; i--)
#define Rof(i, n) for (int i = n-1; i >= 0; i--)
#define FORI(i, n) for (auto i : n)
#define ll long long
#define ull unsigned long long
#define vi vector <int>
#define vl vector <ll>
#define pii pair <int, int>
#define pll pair <ll, ll>
#define mk make_pair
#define ff first
#define ss second
#define eb emplace_back
#define em emplace
#define pb push_back
#define ppb pop_back
#define All(a) a.begin(), a.end()
#define memo(a, b) memset(a, b, sizeof a)
#define Sort(a) sort(All(a))
#define ED(a) Sort(a), a.erase(unique(All(a)), a.end())
#define rev(a) reverse(All(a))
#define sz(a) (int)a.size()
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define maxAll(a) *max_element(All(a))
#define minAll(a) *min_element(All(a))
#define allUpper(a) transform(All(a), a.begin(), :: toupper)
#define allLower(a) transform(All(a), a.begin(), :: tolower)
#define endl '\n'
#define nl puts("")
#define ub upper_bound
#define lb lower_bound
#define Exp exp(1.0)
#define PIE 2*acos(0.0)
#define Sin(a) sin(((a)*PIE)/180.0)
#define EPS 1e-9
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
using namespace __gnu_pbds;
template <typename T> using orderset = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
// int dr[] = {1, -1, 0, 0}; // 4 Direction
// int dc[] = {0, 0, 1, -1};
// int dr[] = {0, 0, 1, -1, 1, 1, -1, -1}; // 8 Direction
// int dc[] = {1, -1, 0, 0, 1, -1, 1, -1};
// int dr[] = {-1, 1, -2, -2, -1, 1, 2, 2}; // knight Moves
// int dc[] = {-2, -2, -1, 1, 2, 2, 1, -1};
#define trace1(x) cerr << #x << ": " << x << endl;
#define trace2(x, y) cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z) cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
inline int setbit(int mask, int pos) { return mask |= (1 << pos); }
inline int resetbit(int mask, int pos) { return mask &= ~(1 << pos); }
inline int togglebit(int mask, int pos) { return mask ^= (1 << pos); }
inline bool checkbit(int mask, int pos) { return (bool)(mask & (1 << pos)); }
#define popcount(mask) __builtin_popcount(mask) // count set bit
#define popcountLL(mask) __builtin_popcountll(mask) // for long long
inline int read() { int a; scanf("%d", &a); return a; }
inline ll readLL() { ll a; scanf("%lld", &a); return a; }
inline double readDD() { double a; scanf("%lf", &a); return a; }
template <typename T> string toString(T num) { stringstream ss; ss << num; return ss.str(); }
int toInt(string s) { int num; istringstream iss(s); iss >> num; return num; }
ll toLLong(string s) { ll num; istringstream iss(s); iss >> num; return num; }
#define inf 1e17
#define mod 1000000007
static const int maxn = 2e4 + 5;
static const int logn = 18;
struct FragmentedTree
{
#define VI vector <int>
#define VL vector <ll>
#define VVI vector <VI>
#define pb push_back
#define sz(a) (int)a.size()
VVI adj; // adjacency list of the fragmented tree
VVI adj2; // adjacency list of all the special nodes
int N; // total node in the tree
int SQ; // sqrt(total node)
VI L; // level of node u
VI P; // parent of node u
VI G; // which fragment the node is
VI SZ; // subtree of of node u
VL V; // result of subtree u
struct Fragment
{
int u; // node
int p; // parent
int maxL; // maximum level
int N; // total node in the tree
VI nodes; // nodes under this fragment
VI &L; // level of node u in the tree
VI lvlFrec; // level frequency
ll tot; // result of this fragment
VL &V; // ans of a particular level
Fragment(int u, int N, VL &V, VI &L) : u(u), N(N), V(V), L(L)
{
p = -1;
tot = 0;
maxL = -1;
}
inline void add(int v)
{
int newlvl = L[v] - L[u];
nodes.pb(v);
if(v >= N) return; // special node
if(newlvl > maxL)
{
maxL = newlvl;
lvlFrec.resize(maxL+1);
}
lvlFrec[newlvl]++;
}
inline void update(int lvl, ll v)
{
int newlvl = lvl - L[u];
if(newlvl < 0 || newlvl > maxL) return;
tot += v * lvlFrec[newlvl];
}
inline ll query()
{
return tot;
}
};
vector<Fragment> frags;
FragmentedTree(int N) : N(N), adj(N), P(N,-1), L(N), G(N,-1), V(N), SZ(N)
{
SQ = max((int)sqrt(N),2);
}
inline void addEdge(int u, int v)
{
adj[u].pb(v);
}
inline ll getSum(int u)
{
if(leader(u) == u)
{
ll w = frags[ G[u] ].query();
for(int g : adj2[ G[u] ])
{
w += getSum(frags[g].u);
}
return w;
}
else
{
ll w = V[ L[u] ];
for(int v : adj[u])
{
w += getSum(v);
}
return w;
}
}
inline void update(int LVL, ll v)
{
V[LVL] += v;
for(Fragment &f : frags)
{
f.update(LVL, v);
}
}
inline int createNode(int u, VI nex)
{
G.pb(-1);
P.pb(u);
L.pb(u <= 0 ? 0 : L[u]+1);
int nn = sz(adj);
adj.pb(nex);
return nn;
}
inline void dfsL(int u, int LVL = 0)
{
L[u] = LVL;
SZ[u] = 1;
for(int v : adj[u])
{
dfsL(v, LVL+1);
SZ[u] += SZ[v];
}
}
inline void buildFragment(int u, Fragment &F)
{
if(G[u] != -1) return;
G[u] = sz(frags) - 1;
F.add(u);
for(int v : adj[u])
{
buildFragment(v, F);
}
}
inline void fragment()
{
dfsL(0);
VVI nodesByLevel(N);
for(int i = 0; i < N; ++i) nodesByLevel[ N-1-L[i] ].pb(i);
for(VI p : nodesByLevel)
{
for(int u : p)
{
VI toF;
VI temp, child = adj[u], spChild;
int sz = 0;
SZ[u] = 1;
for(int v : child)
{
SZ[u] += SZ[v];
}
for(int v : child)
{
sz += SZ[v];
temp.pb(v);
if(sz > SQ)
{
int nn = createNode(u, temp);
temp.clear();
spChild.pb(nn);
frags.pb(Fragment(nn, N, V, L));
buildFragment(nn, frags.back());
SZ[u] -= sz;
sz = 0;
}
}
adj[u] = temp;
for(int v : spChild) adj[u].pb(v);
}
}
int nn = createNode(-1, VI(1,0));
frags.pb(Fragment(nn, N, V, L));
buildFragment(nn, frags.back());
adj2 = VVI(sz(frags));
for(int i = 0; i < frags.size(); ++i)
{
Fragment &f = frags[i];
if(P[f.u] == -1) continue;
f.p = G[ P[f.u] ];
adj2[ f.p ].pb(i);
}
}
inline int leader(int u)
{
return frags[G[u]].u;
}
inline int lca(int u,int v)
{
while(leader(u) != leader(v))
{
if(L[ leader(u) ] > L[ leader(v)])
{
u = P[ leader(u) ];
}
else
{
v = P[ leader(v) ];
}
}
while(u != v)
{
if(L[v] > L[u])
{
v = P[v];
}
else
{
u = P[u];
}
}
return u;
}
// inline void dfs(int u = 0, int p = -1)
// {
// cerr << p << " ----> " << u << " = " << G[u] << " : " << frags[ G[u] ].u << endl;
// for (int v : adj[u])
// {
// if (v == p) continue;
// dfs(v, u);
// }
// }
// inline void showFragments()
// {
// for (Fragment f : frags)
// {
// cout << "u = " << f.u << endl;
// cerr << "p = " << f.p << endl;
// cerr << "maxL = " << f.maxL << endl;
// cerr << "N = " << f.N << endl;
// cerr << "nodes = "; for (int v : f.nodes) cerr << v << " "; cerr << endl;
// cerr << "L = " ; for (int v : f.L) cerr << v << " "; cerr << endl;
// cerr << "lvlFrec = " ; for(int v : f.lvlFrec) cerr << v << " "; cerr << endl;
// cerr << "tot = " << f.tot << endl;
// cerr << "V = "; for (int v : V) cerr << v << " "; cerr << endl;
// cerr << "\n======================\n";
// }
// }
};
int main()
{
// FI;
int N = read();
int M = read();
FragmentedTree FT(N);
for(int e = 1; e < N; e++)
{
int u = read();
int v = read();
u--;
v--;
FT.addEdge(u,v); // Directed Tree
}
FT.fragment();
// FT.dfs();
// FT.showFragments();
for(int i = 0; i < M; ++i)
{
int type = read();
if(type == 1)
{
int L = read();
ll Y = readLL();
FT.update(L, Y);
}
else
{
int X = read();
X--;
printf("%lld\n", FT.getSum(X));
}
}
}
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.