結果
問題 | No.399 動的な領主 |
ユーザー |
![]() |
提出日時 | 2024-10-04 04:40:41 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 359 ms / 2,000 ms |
コード長 | 9,370 bytes |
コンパイル時間 | 4,004 ms |
コンパイル使用メモリ | 281,584 KB |
実行使用メモリ | 31,648 KB |
最終ジャッジ日時 | 2024-10-04 04:40:52 |
合計ジャッジ時間 | 8,823 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 19 |
ソースコード
#ifdef t9unkubj#include"template.h"//#include"template_no_debug.h"#else#undef _GLIBCXX_DEBUG#pragma GCC optimize("O3")#define dbg(...) 199958using namespace std;#include<bits/stdc++.h>using uint=unsigned;using ll=long long;using ull=unsigned long long;using ld=long double;using pii=pair<int,int>;using pll=pair<ll,ll>;template<class T>using vc=vector<T>;template<class T>using vvc=vc<vc<T>>;template<class T>using vvvc=vvc<vc<T>>;using vi=vc<int>;using vvi=vc<vi>;using vvvi=vc<vvi>;using vl=vc<ll>;using vvl=vc<vl>;using vvvl=vc<vvl>;template<class T>using smpq=priority_queue<T,vector<T>,greater<T>>;template<class T>using bipq=priority_queue<T>;#define rep(i,n) for(ll i=0;i<(ll)(n);i++)#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)#define drep(i,n) for(ll i=((n)-1);i>=0;i--)#define all(x) x.begin(),x.end()#define rall(x) x.rbegin(),x.rend()#define mp make_pair#define pb push_back#define eb emplace_back#define fi first#define se second#define is insert#define bg begin()#define ed end()void scan(int&a) { cin >> a; }void scan(ll&a) { cin >> a; }void scan(string&a) { cin >> a; }void scan(char&a) { cin >> a; }void scan(uint&a) { cin >> a; }void scan(ull&a) { cin >> a; }void scan(bool&a) { cin >> a; }void scan(ld&a){ cin>> a;}template<class T> void scan(vector<T>&a) { for(auto&x:a) scan(x); }void read() {}template<class Head, class... Tail> void read(Head&head, Tail&... tail) { scan(head); read(tail...); }#define INT(...) int __VA_ARGS__; read(__VA_ARGS__);#define LL(...) ll __VA_ARGS__; read(__VA_ARGS__);#define ULL(...) ull __VA_ARGS__; read(__VA_ARGS__);#define STR(...) string __VA_ARGS__; read(__VA_ARGS__);#define CHR(...) char __VA_ARGS__; read(__VA_ARGS__);#define DBL(...) double __VA_ARGS__; read(__VA_ARGS__);#define LD(...) ld __VA_ARGS__; read(__VA_ARGS__);#define VC(type, name, ...) vector<type> name(__VA_ARGS__); read(name);#define VVC(type, name, size, ...) vector<vector<type>> name(size, vector<type>(__VA_ARGS__)); read(name);void print(int a) { cout << a; }void print(ll a) { cout << a; }void print(string a) { cout << a; }void print(char a) { cout << a; }void print(uint a) { cout << a; }void print(bool a) { cout << a; }void print(ull a) { cout << a; }void print(double a) { cout << a; }void print(ld a){ cout<< a; }template<class T> void print(vector<T>a) { for(int i=0;i<(int)a.size();i++){if(i)cout<<" ";print(a[i]);}cout<<endl;}void PRT() { cout <<endl; return ; }template<class T> void PRT(T a) { print(a); cout <<endl; return; }template<class Head, class... Tail> void PRT(Head head, Tail ... tail) { print(head); cout << " "; PRT(tail...); return; }template<class T,class F>bool chmin(T &x, F y){if(x>y){x=y;return true;}return false;}template<class T, class F>bool chmax(T &x, F y){if(x<y){x=y;return true;}return false;}void YesNo(bool b){cout<<(b?"Yes":"No")<<endl;}void Yes(){cout<<"Yes"<<endl;}void No(){cout<<"No"<<endl;}template<class T>int popcount(T n){return __builtin_popcountll(n);}template<class T>T sum(vc<T>&a){return accumulate(all(a),T(0));}template<class T>T max(vc<T>&a){return *max_element(all(a));}template<class T>T min(vc<T>&a){return *min_element(all(a));}template<class T>void unique(vc<T>&a){a.erase(unique(all(a)),a.end());}vvi readgraph(int n,int m,int off = -1){vvi g(n);rep(i, m){int u,v;cin>>u>>v;u+=off,v+=off;g[u].push_back(v);g[v].push_back(u);}return g;}vvi readtree(int n,int off=-1){return readgraph(n,n-1,off);}template<class T>vc<T> presum(vc<T> &a){vc<T> ret(a.size()+1);rep(i,a.size())ret[i+1]=ret[i]+a[i];return ret;}template<class T, class F>vc<T> &operator+=(vc<T> &a,F b){for (auto&v:a)v += b;return a;}template<class T, class F>vc<T> &operator-=(vc<T>&a,F b){for (auto&v:a)v-=b;return a;}template<class T, class F>vc<T> &operator*=(vc<T>&a,F b){for (auto&v:a)v*=b;return a;}#endiftemplate<class T>struct dual_seg{int n;using F=function<T(T,T)>;F op;T id;vector<T>lazy;int log=0;dual_seg(int n_,F op,T id):n(n_),op(op),id(id){while((1<<log)<n_)log++;n=1<<log;lazy=vector<T>(n*2,id);}void set(int i,T x){assert(0<=i&&i<n);for(int j=log;j>=1;j--){push(i>>j);}lazy[i]=x;}void apply(int l,int r,T x){assert(0<=l&&l<=r&&r<=n);if(l==r)return;l+=n,r+=n;for(int i=log;i>=1;i--){if(((l>>i)<<i)!=l)push(l>>i);if(((r>>i)<<i)!=r)push((r-1)>>i);}while(l<r){if(l&1)all_apply(l++,x);if(r&1)all_apply(--r,x);l>>=1,r>>=1;}}T get(int i){assert(0<=i&&i<n);i+=n;for(int j=log;j>=1;j--){push(i>>j);}return lazy[i];}void push(int k){all_apply(k*2,lazy[k]),all_apply(k*2+1,lazy[k]);lazy[k]=id;}void all_apply(int k,T x){lazy[k]=op(lazy[k],x);}};#include<vector>#include<cassert>#include<algorithm>struct HLD{int n;std::vector<int>depth,head,siz_,par,in,out;std::vector<std::vector<int>>g,c;HLD(int n):n(n),depth(n),head(n),siz_(n,1),in(n),out(n),g(n),c(n){}HLD(int n,std::vector<std::vector<int>>g):n(n),depth(n),head(n),siz_(n,1),in(n),out(n),g(g),c(n){}int inited=0;void add_edge(int u,int v,bool d=0){g[u].emplace_back(v);if(d)g[v].emplace_back(u);}void init_dfs1(int now,int pre){for(int &x:g[now]){if(x==pre)continue;c[now].emplace_back(x);depth[x]=depth[now]+1;par[x]=now;init_dfs1(x,now);siz_[now]+=siz_[x];}}void init_dfs2(int now,int pre,int&order){in[now]=order++;for(int i=0;i<(int)c[now].size();i++){if(siz_[c[now][0]]<siz_[c[now][i]])std::swap(c[now][0],c[now][i]);}for(int x:c[now]){if(x==c[now][0])head[x]=head[now];else head[x]=x;init_dfs2(x,now,order);}out[now]=order++;}void init(int root=0){//rootからの有向辺にになることに注意par=head=std::vector<int>(n,root);int order{};init_dfs1(root,-1);init_dfs2(root,-1,order);}int lca(int u,int v){//O(logN) u,vのlcaを取得するif(head[u]==head[v])return (depth[u]>depth[v]?v:u);if(depth[head[u]]>depth[head[v]])std::swap(u,v);v=par[head[v]];return lca(u,v);}int f1(int a){//入った時間を返すO(1)return in[a];}int f2(int a){//出た時間を返すO(1)return out[a];}int dis(int u,int v){//uとvの最短距離を求めるO(logN)assert(0<=u&&u<n);assert(0<=v&&v<n);return depth[u]+depth[v]-2*depth[lca(u,v)];}template<class T,class G>void set(int u,T&seg,G x){seg.set(f1(u),x);}template<class T,class G>G prod(int u,int v,bool edge,T&seg){//[u,v]の演算結果を取得する,G>ret T>seg木 O(log^2N)G sml=seg.e,smr=seg.e;while(1){if(in[u]>in[v])swap(u,v),swap(sml,smr);if(head[u]==head[v])break;smr=seg.op(smr,seg.prod(in[head[v]],in[v]+1));v=par[head[v]];}return seg.op(sml,seg.op(smr,seg.prod(in[u]+edge,in[v]+1)));}template<class T>void ap(int u,int v,bool edge,T&seg){//[u,v]の演算結果を取得する,G>ret T>seg木 O(log^2N)//G sml=seg.e,smr=seg.e;while(1){if(in[u]>in[v])swap(u,v);//swap(sml,smr);if(head[u]==head[v])break;//smr=seg.op(smr,seg.prod(in[head[v]],in[v]+1));seg.apply(in[head[v]],in[v]+1,1);v=par[head[v]];}seg.apply(in[u]+edge,in[v]+1,1);//return seg.op(sml,seg.op(smr,seg.prod(in[u]+edge,in[v]+1)));}vector<vector<int>>db;void la_init(){int log=0;while((1<<log)<n)log++;db.resize(log,vector<int>(n));db[0]=par;for(int i=1;i<log;i++){for(int j=0;j<n;j++){int nxt=db[i-1][j];if(nxt==-1)db[i][j]=-1;else{db[i][j]=db[i-1][nxt];}}}}int la(int x,int p){int now=0;while(p){if(p&1)x=db[now][x];p>>=1;now++;if(x==-1)return -1;}return x;}};double pass_time=0;void solve(){INT(n);auto g=readtree(n);dual_seg<ll>seg(n*2,[](ll a,ll b){return a+b;},0);HLD hld(n,g);hld.init(0);INT(q);while(q--){INT(a,b);--a,--b;hld.ap<dual_seg<ll>>(a,b,0,seg);}ll ans=0;rep(i,n*2)ans+=seg.get(i)*(seg.get(i)+1)/2;PRT(ans);}signed main(){cin.tie(0)->sync_with_stdio(0);pass_time=clock();int t=1;//cin>>t;while(t--)solve();pass_time=clock()-pass_time;dbg(pass_time/CLOCKS_PER_SEC);}