Codeforce gym: 101484 F. No Link, Cut Tree!

Problem Link : http://codeforces.com/gym/101484/problem/F

Solution Idea:

    My solution idea for this problem is at first make the given tree a full binary tree. A full binary tree (sometimes proper binary tree or 2-tree) is a tree in which every node other than the leaves has two children. On the other hand A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. So we can convert a complete binary tree to a full binary tree by adding some dummy node whose cost is 0 so that they don’t contribute anything in the solution as well as they will help us to form our solution.

    Now classify the nodes according to their level and make their cumulative sum or insert them in segment tree or in a binary indexed tree. We need this data structure for every level. Now map the nodes by the inorder traversal of the tree and position of the level array like 1,2,3….

    Now here comes an important observation in a full binary tree at any level, if I want to delete a subtree starting at node u the will need to delete 1 node from level[u], 2 node from level[u]+1, 4 node from level[u]+2…2^i node form level[u]+i.

    Now form the data structure (here I have used Binary Indexed Tree(BIT)) just query the contribution of the deleted node subtract them form the total contribution of that level and take the maximum. We need to do this from level[u] to last level and we need to consider the whole level from level 1 to level[u]-1.


#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cerr<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define LINE_PRINT_CASE  printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

#define mx 200005

vector<int>g[mx];

vector<int>level_g[20];

int map1[mx],levell[mx];
int map2_level[mx],cost[mx],max_depth,disc;
int tree[20][mx];
int n,m;


void dfs1(int u, int level)
{
    max_depth=max(max_depth,level);
    for(int i=0;i<SZ(g[u]);i++)
    {
        int v=g[u][i];
        dfs1(v,level+1);
    }
}

void dfs(int u, int par, int level)
{
    levell[u]=level;
//    max_depth=max(max_depth,level);
    map1[u]=++disc;
    level_g[level].pb(u);

    if(levell[u]!=max_depth)
    {
        if(SZ(g[u])==0)
            g[u].pb(++n);
        if(SZ(g[u])==1)
            g[u].pb(++n);
    }

    for(int i=0;i<SZ(g[u]);i++)
    {
        int v=g[u][i];
        if(v==par) continue;
        dfs(v,u,level+1);
    }
}



void update(int id, int idx, int val)
{
    for(int i=idx;i<mx;i+=(i&-i))
        tree[id][i]+=val;
}

int query(int id, int idx)
{
    int ret=0;
    for(int i=idx;i>0;i-=(i&-i))
        ret+=tree[id][i];
    return ret;
}

int main()
{
//    freopen("in.txt","r",stdin);
//	  freopen("out.txt","w",stdout);


    sff(n,m);
    sf(cost[1]);

    for(int i=1;i<n;i++)
    {
        int a,b,c;
        sfff(a,b,c);
        g[b].pb(a);
        cost[a]=c;
    }
    dfs1(1,1);
//    int xx=n;
//    for(int i=1;i<=xx;i++)
//    {
//        if(SZ(g[i])==1)
//            g[i].pb(++n);
//    }

    dfs(1,1,1);

    for(int i=1;i<=max_depth;i++)
    {
        int num=0;
        for(int j=0;j<SZ(level_g[i]);j++)
        {
            int v=level_g[i][j];
            map2_level[map1[v]]=++num;
            update(i,num,cost[v]);
        }
    }

    while(m--)
    {
        int u;
        sf(u);
        int ans=0;
        for(int i=1;i<levell[u];i++)
            ans=max(ans,query(i,mx-1));
        int last=levell[u],pp=0,cur=map1[u];
        for(int i=levell[u];i<=max_depth;i++)
        {
            int total=query(i,mx-1);
            int sub=query(i,map2_level[cur]+(1<<pp)-1);
            int sub1=query(i,map2_level[cur]-1);
            total-=(sub-sub1);
            ans=max(ans,total);
            pp++;
            cur++;
        }

        printf("%d\n",ans);

    }



    return 0;
}

Advertisements