#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair P; struct LinkCutTree{ struct Node{ Node *l, *r, *p; bool rev; int idx, val, sz, szl; ll cost, sum, suml, costs, sum2; Node(int val, int idx, ll cost):cost(cost), costs(cost), sum(0), sum2(0), suml(0), idx(idx), val(val), sz(val), szl(0), rev(false), l(nullptr), r(nullptr), p(nullptr){} bool is_root(){ return !p || (p->l!=this && p->r!=this); } }; vector v; LinkCutTree(int n){ v.resize(n); for(int i=0; isum, t->sum2); swap(t->l, t->r); t->rev^=true; } void push(Node *t){ if(!t) return; if(t->rev){ toggle(t->l); toggle(t->r); t->rev=false; } } void update(Node *t){ t->sz=t->val+t->szl, t->costs=t->cost; if(t->l) t->sz+=t->l->sz, t->costs+=t->l->costs; if(t->r) t->sz+=t->r->sz, t->costs+=t->r->costs; t->sum=t->suml+t->cost*t->szl; t->sum2=t->suml+t->cost*t->szl; if(t->l) t->sum+=t->l->sum, t->sum2+=t->l->sum2, t->sum+=t->l->costs*(t->val+t->szl), t->sum2+=t->l->sz*t->cost; if(t->r) t->sum+=t->r->sum, t->sum2+=t->r->sum2, t->sum+=t->r->sz*t->cost, t->sum2+=t->r->costs*(t->val+t->szl); if(t->l && t->r) t->sum+=t->l->costs*t->r->sz, t->sum2+=t->r->costs*t->l->sz; } void rotate(Node *t){ Node *p=t->p, *pp=p->p, *ch; if(p->l==t) ch=t->r; else ch=t->l; if(pp){ if(pp->l==p) pp->l=t; else if(pp->r==p) pp->r=t; } t->p=pp; if(p->l==t) t->r=p; else t->l=p; p->p=t; if(p->l==t) p->l=ch; else p->r=ch; if(ch) ch->p=p; update(p); update(t); } int state(Node *t){ if(t->is_root()) return 0; else if(t->p->l==t) return 1; else return -1; } void splay(Node *t){ push(t); while(state(t)){ if(!state(t->p)){ push(t->p); push(t); rotate(t); }else{ push(t->p->p); push(t->p); push(t); if(state(t->p)==state(t)){ rotate(t->p); rotate(t); }else{ rotate(t); rotate(t); } } } } Node *expose(Node *t){ Node *rp=nullptr; for(Node *now=t; now; now=now->p){ splay(now); if(rp){ now->szl-=rp->sz; now->suml-=rp->sum; } if(now->r){ now->szl+=now->r->sz; now->suml+=now->r->sum; } now->r=rp; update(now); rp=now; } splay(t); return rp; } void link(Node *c, Node *p){ expose(c); expose(p); p->r=c; c->p=p; update(p); } void cut(Node *c){ expose(c); c->l->p=nullptr; c->l=nullptr; update(c); } void evert(Node *t){ expose(t); toggle(t); push(t); } }; int main() { int n, k, q; scanf("%d %d %d", &n, &k, &q); LinkCutTree lct(n); using node=LinkCutTree::Node; int c[100010]; for(int i=0; ival++; } for(int i=0; ival--; c[p]=d; lct.expose(lct.v[c[p]]); lct.v[c[p]]->val++; }else{ int e; scanf("%d", &e); e--; lct.evert(lct.v[e]); printf("%lld\n", lct.v[e]->sum); } } return 0; }