[題解]樹狀圖分析

a123. 樹狀圖分析

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define lld long long
#define N 100005
using namespace std;
int n,father[N],h[N];

vector<int>edge[N];

void dfs(int cur){
    int maxn = 0;
    for(auto next:edge[cur]){
        dfs(next);
        maxn = max(maxn,h[next]+1);
    }
    h[cur] = maxn;
}

signed main(){
    ios;
    memset(h,0,sizeof(h));
    memset(father,0,sizeof(father));
    
    cin>>n;
    for(int i=1;i<=n;i++){
        int k;cin>>k;
        for(int j=0;j<k;j++){
            int temp;cin>>temp;
            edge[i].push_back(temp);
            father[temp] = i;
        }
    }
    int root = 1;
    while(father[root]!=0)root++;
    
    dfs(root);
    
    lld ans = 0;
    for(int i=1;i<=n;i++)ans += h[i];
    
    cout<<root<<endl<<ans<<endl;
}


//O(N)的作法
#include <bits/stdc++.h>
#define lld long long
using namespace std;
lld n,m;

int main(){
    int t;scanf("%d",&t);
    while(t--){
        int n,m,ans = 1;scanf("%d %d",&n,&m);
        m--;    //從0開始
        for(int i=1;i<n;i++){         //共n-1步要走
            if(m&1)ans = ans*2+1;     //往右邊走
            else ans = ans*2;
            m = m>>1;                 //由低bit到高bit決定每一步要怎麼走
        }
        printf("%lld\n",ans);
    }
}