結果

問題 No.399 動的な領主
ユーザー tempura_pptempura_pp
提出日時 2018-08-15 02:12:30
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 145 ms / 2,000 ms
コード長 3,991 bytes
コンパイル時間 1,030 ms
コンパイル使用メモリ 103,860 KB
実行使用メモリ 13,568 KB
最終ジャッジ日時 2024-09-24 09:17:48
合計ジャッジ時間 3,582 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 3 ms
6,944 KB
testcase_05 AC 12 ms
6,944 KB
testcase_06 AC 140 ms
12,800 KB
testcase_07 AC 143 ms
12,672 KB
testcase_08 AC 145 ms
12,800 KB
testcase_09 AC 138 ms
12,672 KB
testcase_10 AC 3 ms
6,944 KB
testcase_11 AC 11 ms
6,944 KB
testcase_12 AC 112 ms
13,184 KB
testcase_13 AC 107 ms
13,312 KB
testcase_14 AC 62 ms
13,568 KB
testcase_15 AC 62 ms
13,440 KB
testcase_16 AC 72 ms
13,184 KB
testcase_17 AC 142 ms
12,800 KB
testcase_18 AC 134 ms
12,672 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:167:13: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  167 |        scanf("%d%d",&x,&y);
      |        ~~~~~^~~~~~~~~~~~~~
main.cpp:174:13: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  174 |        scanf("%d%d",&x,&y);
      |        ~~~~~^~~~~~~~~~~~~~

ソースコード

diff # 

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;
int dx[4]={1,0,-1,0} , dy[4]={0,1,0,-1} ;


struct BIT{
private:
   int sz;
   vector<ll> node;
public:
   BIT(int n):sz(n),node(n+1){};
   void add(int k,ll x){
       k++;
       while(k<=sz){
           node[k]+=x;
           k+=k&-k;
       }
   }
   ll sum(int k){
       k++;
       ll ret=0;
       while(k>0){
           ret+=node[k];
           k-=k&-k;
       }
       return ret;
   }
   ll sum(int l,int r){
       return sum(r-1)-sum(l-1);
   }
   ll get(int k){
       return sum(k,k+1);
   }
};

BIT bit(101010);
struct HLDecomposition{
    int n,pos;
    vector<vector<int>> v;
    vector<int> idx,head,sz,hvy,par,depth,inv,type;

    HLDecomposition(){};
    HLDecomposition(int s):
        n(s),pos(0),v(n),idx(n,-1),head(n),sz(n,1),
        hvy(n,-1),par(n),depth(n),inv(n),type(n){}
    
    void addedge(int x,int y){
        v[x].push_back(y);
        v[y].push_back(x);
    }

    void dfs1(int rt){
        par[rt]=-1;
        depth[rt]=0;
        stack<pint> st;
        st.push({rt,0});
        while(!st.empty()){
            int x=st.top().first;
            int& i=st.top().second;
            if(i<(int)v[x].size()){
                int to=v[x][i++];
                if(to==par[x])continue;
                par[to]=x;
                depth[to]=depth[x]+1;
                st.push({to,0});
            }
            else {
                st.pop();
                int res=0;
                for(int to:v[x]){
                    if(to==par[x])continue;
                    sz[x]+=sz[to];
                    if(sz[to]>res)res=sz[to],hvy[x]=to;
                }
            }
        }
    }
    void dfs2(int r,int c){
        int &k=pos;
        stack<int> st;
        st.push(r);
        while(!st.empty()){
            int h=st.top();st.pop();
            for(int x=h;x!=-1;x=hvy[x]){
                type[x]=c;
                head[x]=h;
                idx[x]=k++;
                inv[idx[x]]=x;
                for(int to:v[x])
                    if(to!=par[x]&&to!=hvy[x])st.push(to);
            }
        }
    }

    void build(vector<int> rs=vector<int>(1,0)){
        int c=0;
        for(int r:rs){
            dfs1(r);
            dfs2(r,c++);
        }
    }
    void f(int x,int y){
        //ここに何か書く！！！
        bit.add(x,1);
        bit.add(y+1,-1);
    }

    void for_v(int x,int y){
        while(1){
            if(idx[x]>idx[y])swap(x,y);
            f(max(idx[head[y]],idx[x]),idx[y]);
            if(head[x]!=head[y])y=par[head[y]];
            else break;
        }
    }

    void for_edge(int x,int y){
        while(1){
            if(idx[x]>idx[y])swap(x,y);
            if(head[x]!=head[y]){
                f(idx[head[y]],idx[y]);
                y=par[head[y]];
            }
            else{
                if(x!=y)f(idx[x]+1,idx[y]);
                break;
            }
        }
    }
    int lca(int x,int y){
        while(1){
            if(idx[x]>idx[y])swap(x,y);
            if(head[x]==head[y])return x;
            y=par[head[y]];
        }
    }

    int dist(int x,int y){
        return depth[x]+depth[y]-2*depth[lca(x,y)];
    }
};
int main(){
   int n;cin>>n;
   HLDecomposition hl(n);
   rep(i,n-1){
       int x,y;
       scanf("%d%d",&x,&y);
       hl.addedge(x-1, y-1);
   }
   hl.build();
   int q;cin>>q;
   rep(i,q){
       int x,y;
       scanf("%d%d",&x,&y);
       hl.for_v(x-1,y-1);
   }
   ll ans=0;
   rep(i,n){
       ll ret=bit.sum(i);
       ans+=ret*(ret+1)/2;
   }
   cout<<ans<<endl;
   return 0;
}
0