Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma comment(linker,"/STACK:256000000")
- #include <cstdlib>
- #include <ctime>
- #include <cstdio>
- #include <map>
- #include <set>
- #include <sstream>
- #include <string>
- #include <iostream>
- #include <utility>
- #include <queue>
- #include <cmath>
- #include <stack>
- #include <memory.h>
- #include <algorithm>
- using namespace std;
- #define forn(i,n) for(int i=0;i<(n);++i)
- #define fornr(i,n) for(int i=(n)-1;i>=0;--i)
- #define forv(i,v) forn(i,(int)v.size())
- #define fors(i,v) forn(i,(int)v.length())
- #define forvr(i,v) fornr(i,(int)v.size())
- #define mp make_pair
- #define pb push_back
- #define lng long long
- #define SQ(a) ((a)*(a))
- #define eps 1e-9
- #define VI vector<int>
- #define PII pair<int, int>
- #define all(v) (v).begin(),(v).end()
- #define iinf 1000000000
- #define linf 1000000000000000000LL
- #define pi 3.1415926535897932384626433832795
- #define inp asdinp
- #define prev asdprev
- struct tree
- {
- vector<int> t;
- int n;
- tree(int n)
- {
- this->n = n;
- t = vector<int> (n*6);
- }
- int get(int l, int r, int i, int tl, int tr)
- {
- if (l==tl && r==tr)
- return t[i];
- int m = (tl+tr)/2;
- if (r<=m)
- return get(l, r, i*2+1, tl, m);
- if (l>m)
- return get(l, r, i*2+2, m+1, tr);
- return get(l, m, i*2+1, tl, m) + get(m+1, r, i*2+2, m+1, tr);
- }
- tree(){}
- void update(int pos, int val, int i, int l, int r)
- {
- if (l==r)t[i] = val;
- else
- {
- int m = (l+r)/2;
- if (pos<=m)
- update(pos, val, i*2+1, l, m);
- else
- update(pos, val, i*2+2, m+1, r);
- t[i]=t[2*i+1]+t[2*i+2];
- }
- }
- };
- tree trees[100000+10];
- int type[100000+10];
- int query_a[100000+10];
- int query_b[100000+10];
- char s[10];
- vector<int> graph[100000+10];
- int maxlev[100000+10];
- vector<int> level[100000+10];
- int go[100000+10][20];
- int vlevel[100000+10];
- int vidx[100000+10];
- int levels_cnt=0;
- int dfs(int v, int parent, int lev)
- {
- levels_cnt=max(levels_cnt, lev);
- level[lev].pb(v);
- vidx[v]=level[lev].size()-1;
- vlevel[v]=lev;
- int maxlevel=0;
- int first=-1;
- forv(i, graph[v])
- {
- if (graph[v][i]!=parent)
- {
- if (first==-1)first=graph[v][i];
- maxlevel = max(dfs(graph[v][i], v, lev+1), maxlevel);
- }
- }
- go[v][0]=first;
- maxlev[v]=maxlevel;
- return maxlev[v]+1;
- }
- int solve(int v, int d)
- {
- if (vlevel[v]+d>maxlev[v]+1)
- {
- return 0;
- }
- int left = v;
- forn(i, 30)
- {
- if (d&(1<<i))
- {
- left = go[left][i];
- }
- }
- left = vidx[left];
- int right=-1;
- if (vidx[v]==level[vlevel[v]].size()-1)
- {
- right=level[vlevel[v]+d].size()-1;
- }
- else
- {
- right = level[vlevel[v]][vidx[v]+1];
- forn(i, 30)
- {
- if (d&(1<<i))
- {
- if (right!=-1)right = go[right][i];
- }
- }
- if (right!=-1)
- right = vidx[right]-1;
- }
- if (right==-1)
- right = level[vlevel[v]+d].size()-1;
- return trees[vlevel[v]+d].get(left, right, 0, 0, level[vlevel[v]+d].size()-1);
- }
- #define filename "firm"
- int main(int argc, char *argv[])
- {
- #ifdef __ASD__
- freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
- #else
- freopen(filename".in", "r", stdin);freopen(filename".out", "w", stdout);
- #endif
- int n;
- cin >> n;
- gets(s);
- forn(i,n)
- {
- char c;
- int u, v;
- scanf("%c %d %d\n", &c, &u, &v);
- if (c=='Z')
- {
- type[i]=1;
- --u;
- --v;
- graph[u].pb(v);
- graph[v].pb(u);
- query_a[i]=u;
- query_b[i]=v;
- }
- else
- {
- type[i]=2;
- --u;
- query_a[i]=u;
- query_b[i]=v+1;
- }
- }
- memset(go, 255, sizeof(go));
- dfs(0, -1, 0);
- forn(i, levels_cnt+1)
- {
- trees[i]=tree(level[i].size());
- }
- for(int j=1;j<20;++j)
- {
- forn(i,n)
- {
- go[i][j]=go[go[i][j-1]][j-1];
- }
- }
- forn(i,n)
- {
- if (type[i]==1)
- {
- trees[vlevel[query_a[i]]].update(vidx[query_a[i]], 1, 0, 0, level[vlevel[query_a[i]]].size()-1);
- }
- else
- {
- printf("%d\n", solve( query_a[i], query_b[i]));
- }
- }
- cout.flush();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement