結果
| 問題 | No.902 Query ζone |
| ユーザー |
 tko919
|
| 提出日時 | 2022-02-05 04:46:48 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 682 ms / 5,000 ms |
| コード長 | 9,720 bytes |
| コンパイル時間 | 2,793 ms |
| コンパイル使用メモリ | 227,748 KB |
| 最終ジャッジ日時 | 2025-01-27 20:23:38 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 19 |
ソースコード
#line 1 "library/Template/template.hpp"#include <bits/stdc++.h>using namespace std;#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)#define ALL(v) (v).begin(),(v).end()using ll=long long int;const int inf = 0x3fffffff;const ll INF = 0x1fffffffffffffff;template<typename T>inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}template<typename T>inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}#line 2 "library/Utility/fastio.hpp"#include <unistd.h>class FastIO{static constexpr int L=1<<16;char rdbuf[L];int rdLeft=0,rdRight=0;inline void reload(){int len=rdRight-rdLeft;memmove(rdbuf,rdbuf+rdLeft,len);rdLeft=0,rdRight=len;rdRight+=fread(rdbuf+len,1,L-len,stdin);}inline bool skip(){for(;;){while(rdLeft!=rdRight and rdbuf[rdLeft]<=' ')rdLeft++;if(rdLeft==rdRight){reload();if(rdLeft==rdRight)return false;}else break;}return true;}template<typename T,enable_if_t<is_integral<T>::value,int> =0>inline bool _read(T& x){if(!skip())return false;if(rdLeft+20>=rdRight)reload();bool neg=false;if(rdbuf[rdLeft]=='-'){neg=true;rdLeft++;}x=0;while(rdbuf[rdLeft]>='0' and rdLeft<rdRight){x=x*10+(neg?-(rdbuf[rdLeft++]^48):(rdbuf[rdLeft++]^48));}return true;}template<typename T,enable_if_t<is_floating_point<T>::value,int> =0>inline bool _read(T& x){if(!skip())return false;if(rdLeft+20>=rdRight)reload();bool neg=false;if(rdbuf[rdLeft]=='-'){neg=true;rdLeft++;}x=0;while(rdbuf[rdLeft]>='0' and rdbuf[rdLeft]<='9' and rdLeft<rdRight){x=x*10+(rdbuf[rdLeft++]^48);}if(rdbuf[rdLeft]!='.')return true;rdLeft++;T base=.1;while(rdbuf[rdLeft]>='0' and rdbuf[rdLeft]<='9' and rdLeft<rdRight){x+=base*(rdbuf[rdLeft++]^48);base*=.1;}if(neg)x=-x;return true;}inline bool _read(char& x){if(!skip())return false;if(rdLeft+1>=rdRight)reload();x=rdbuf[rdLeft++];return true;}inline bool _read(string& x){if(!skip())return false;for(;;){int pos=rdLeft;while(pos<rdRight and rdbuf[pos]>' ')pos++;x.append(rdbuf+rdLeft,pos-rdLeft);if(rdLeft==pos)break;rdLeft=pos;if(rdLeft==rdRight)reload();else break;}return true;}template<typename T>inline bool _read(vector<T>& v){for(auto& x:v){if(!_read(x))return false;}return true;}char wtbuf[L],tmp[50];int wtRight=0;inline void flush(){fwrite(wtbuf,1,wtRight,stdout);wtRight=0;}inline void _write(const char& x){if(wtRight>L-32)flush();wtbuf[wtRight++]=x;}inline void _write(const string& x){for(auto& c:x)_write(c);}template<typename T,enable_if_t<is_integral<T>::value,int> =0>inline void _write(T x){if(wtRight>L-32)flush();if(x==0){_write('0');return;}else if(x<0){_write('-');if (__builtin_expect(x == std::numeric_limits<T>::min(), 0)) {switch (sizeof(x)) {case 2: _write("32768"); return;case 4: _write("2147483648"); return;case 8: _write("9223372036854775808"); return;}}x=-x;}int pos=0;while(x!=0){tmp[pos++]=char((x%10)|48);x/=10;}rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i];wtRight+=pos;}template<typename T>inline void _write(const vector<T>& v){rep(i,0,v.size()){if(i)_write(' ');_write(v[i]);}}public:FastIO(){}~FastIO(){flush();}inline void read(){}template <typename Head, typename... Tail>inline void read(Head& head,Tail&... tail){assert(_read(head));read(tail...);}template<bool ln=true,bool space=false>inline void write(){if(ln)_write('\n');}template <bool ln=true,bool space=false,typename Head, typename... Tail>inline void write(const Head& head,const Tail&... tail){if(space)_write(' ');_write(head);write<ln,true>(tail...);}};/*** @brief Fast IO*/#line 3 "sol.cpp"struct LinkCutTree{struct Node{Node *L=nullptr,*R=nullptr,*P=nullptr;int size=1,id;bool rev=0;ll val=0,sum=0;Node(int i,ll v):id(i),val(v),sum(v){}void toggle(){swap(L,R);rev^=1;}void eval(){if(rev){if(L)L->toggle();if(R)R->toggle();rev=0;}}void recalc(){size=1;sum=val;if(L){size+=L->size;sum+=L->sum;}if(R){size+=R->size;sum+=R->sum;}}bool isroot(){return !P or (P->L!=this and P->R!=this);}void rotate(){Node *p,*pp,*c;p=P,pp=P->P;if(p->L==this){c=R;R=p;p->L=c;}else{c=L;L=p;p->R=c;}if(pp){if(pp->L==p)pp->L=this;if(pp->R==p)pp->R=this;}P=pp;p->P=this;if(c)c->P=p;p->recalc();recalc();}void splay(){eval();while(!isroot()){Node *q=P;if(q->isroot()){q->eval();eval();rotate();}else{Node *r=q->P;r->eval();q->eval();eval();if(r->L==q){if(q->L==this){q->rotate();rotate();}else{rotate();rotate();}}else{if(q->R==this){q->rotate();rotate();}else{rotate();rotate();}}}}}};using Np=Node*;LinkCutTree(){}Np make(int id,ll v){return new Node(id,v);}Np expose(Np v){Np pre=nullptr;for(Np cur=v;cur;cur=cur->P){cur->splay();cur->R=pre;cur->recalc();pre=cur;}v->splay();return pre;}void link(Np v,Np p){expose(v);expose(p);v->P=p;p->R=v;p->recalc();}void cut(Np v){expose(v);v->L->P=nullptr;v->L=nullptr;v->recalc();}void evert(Np v){expose(v);v->toggle();v->eval();}Np lca(Np u,Np v){expose(u);return expose(v);}Np kth(Np v,int k){expose(v);while(v){v->eval();if(v->L and v->L->size>k)v=v->L;else{if(v->L)k-=v->L->size;if(k==0)return v;k--;v=v->R;}}return nullptr;}}; using Np=LinkCutTree::Np;FastIO io;int main(){int n;io.read(n);LinkCutTree tree;vector<Np> vs(n),es;rep(i,0,n)vs[i]=tree.make(i,0);int ecnt=0;rep(i,0,n-1){int u,v,w;io.read(u,v,w);es.push_back(tree.make(ecnt++,w));tree.evert(vs[u]);tree.link(vs[u],es.back());tree.evert(vs[v]);tree.link(vs[v],es.back());}int q;io.read(q);while(q--){int t;io.read(t);if(t==1){int u,v,w,x;io.read(u,v,w,x);tree.evert(vs[u]);tree.cut(vs[v]);es.push_back(tree.make(ecnt++,x));tree.evert(vs[v]);tree.link(vs[v],es.back());tree.evert(vs[w]);tree.link(vs[w],es.back());}else{int k;io.read(k);vector<int> x(k);io.read(x);sort(ALL(x),[&](int u,int v){tree.evert(vs[0]);int lca=tree.lca(vs[u],vs[v])->id;if(u==lca)return true;if(v==lca)return false;tree.evert(vs[lca]);int pu=tree.kth(vs[u],1)->id;int pv=tree.kth(vs[v],1)->id;return pu<pv;});ll ret=0;rep(i,0,k){int u=x[i],v=x[(i+1)%k];tree.evert(vs[u]);tree.expose(vs[v]);ret+=vs[v]->sum;}io.write(ret/2);}}return 0;}