結果
問題 | No.763 Noelちゃんと木遊び |
ユーザー |
![]() |
提出日時 | 2020-08-27 13:54:02 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 85 ms / 2,000 ms |
コード長 | 1,551 bytes |
コンパイル時間 | 1,751 ms |
コンパイル使用メモリ | 169,484 KB |
実行使用メモリ | 9,984 KB |
最終ジャッジ日時 | 2024-11-07 16:39:42 |
合計ジャッジ時間 | 4,062 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i, n) for (int i = 0; i < (n); i++)#define all(x) (x).begin(), (x).end()using ll = long long;using pii = pair<int, int>;using vi = vector<int>;using vvi = vector<vector<int>>;const ll inf = 1e9;int tree[400005];vi to[100005];void add(int i,int a){int u=i+tree[0];tree[u]+=a;while(u>1){u/=2;tree[u]=min(tree[u*2],tree[u*2+1]);}}void update(int i,int a){int u=i+tree[0];tree[u]=a;while(u>1){u/=2;tree[u]=min(tree[u*2],tree[u*2+1]);}}int mini(){int u=1;while(u<tree[0]){if(tree[1]==tree[u*2]) u=u*2;else u=u*2+1;}return u-tree[0];}int main() {ll n;cin>>n;tree[0]=1;while(tree[0]<n) tree[0]*=2;for(int u=tree[0]+n;u<tree[0]*2;u++) tree[u]=inf;rep(i,n-1){int u,v;cin>>u>>v;u--;v--;to[u].push_back(v);to[v].push_back(u);tree[u+tree[0]]++;tree[v+tree[0]]++;}// rep(i,tree[0]) cout<<tree[i+tree[0]]<<" ";// cout<<endl;for(int u=tree[0]-1;u>=1;u--) tree[u]=min(tree[u*2],tree[u*2+1]);int ans=1;while(tree[1]==1){int d=0;int i=mini();for(int j:to[i]) if(tree[j+tree[0]]!=inf){d=j;break;}i=d;ans+=tree[i+tree[0]]-1;// cout<<i<<endl;update(i,inf);for(int j:to[i]){int u=j+tree[0];if(tree[u]==inf) continue;if(tree[u]==1) update(j,inf);else add(j,-1);}// rep(i,n) cout<<tree[i+tree[0]]<<" ";// cout<<endl;}cout<<ans<<endl;return 0;}