SUBREM - Editorial

dfs
dynamic-programming
editorial
simple
tree
april19

#1

PROBLEM LINK:

Practice
Contest, div. 1
Contest, div. 2

Author: Ashish Gupta
Tester: Zhong Ziqian
Editorialist: Oleksandr Kulkov

DIFFICULTY:
SIMPLE
PREREQUISITES:
DFS
PROBLEM:
You’re given tree on N vertices, each node has assigned value A_i. You may choose any node in the tree and remove all its descendants and the node itself. Your profit for that will be equal to the sum of values still existing in the tree minus X \cdot k where k is number of deletions and X is given number. You have to find the maximum possible profit.
QUICK EXPLANATION:
As simple as dp_v = \max\left(A_v+\sum\limits_{u \in \text{children}_v} dp_u, -X\right).
EXPLANATION:
Maintain dp_v to be best possible sum you may get from subtree of v. You will either drop subtree or not, in first case it’s -X and in second case it’s A_v plus sum of dp_u over all children of v:

int dfs(int v = 1, int p = 1) {
	int res = 0;
	for(auto u: g[v]) {
		if(u != p) {
			res += dfs(u, v);
		}
	}
	return max(A[v] + res, -x);
}

AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.


The Brand New Discuss Forum
#2

My solution also uses dfs and has the exact same logic yet I get TLE on some cases. What am I doing wrong?

#include<bits/stdc++.h>
#define ll long long int
#define li long int
using namespace std;

typedef vector<long long int> vi;
typedef pair<ll, ll> pi;

#define EB emplace_back
#define REP(i, x, y) for(long long int i=x ; i<y ; i++)
#define F first
#define PB push_back
#define S second
#define MP make_pair
#define MT make_tuple
#define INF 9999999
#define MOD 1000000007

struct node{
    ll val;
    vector<ll> children;

};

ll pruneornot( node lol , ll x, vector<node> points, ll visited[])
{
    vector<ll> z =lol.children;
    cout<<lol.val<<" \n";
    ll len = z.size();
    ll sum = 0;
    REP(i,0,len)
    {
        if( visited[z[i]]!=1 )
        {
            visited[ z[i] ]=1;
            sum+= pruneornot( points[z[i]], x , points, visited);
        }
    }
return max(-x , lol.val + sum);

}

int main()
{
ios::sync_with_stdio(0);
ll t;
cin>>t;
while(t–)
{
ll n;
ll x;
cin>>n>>x;
ll visited[n];
vi a(n);
vector points(n);
points.clear();
REP(i,0,n)
{
cin>>a[i];
visited[i]=0;
points[i].val=a[i];
}
ll u,v;
REP(i,0,n-1)
{
cin>>u>>v;
points[u-1].children.emplace_back(v-1);
points[v-1].children.emplace_back(u-1);
}
visited[0]=1;
cout<<pruneornot(points[0], x ,points,visited)<<"\n";

}
return 0;

}


#3

Is there any Greedy approach relevant to this problem ?


#4

My solution is same as editorialist :XD


#5

if anyone can look at this solution why is this wrong ?
https://www.codechef.com/viewplaintext/23985717

so approach is sort every node by increasing order of subtree sum( self included) , now whoever is less than -X , that can be removed as it will yeild positive profit, then i updated parents to accomodate that node removal and update children to have subtree sum 0

also this should be amortized linear , but i got TLE too , did i miss anything


#6

Can someone provide a good test case for the problem, I tried solving it using dictionary and approach similar to given above but got WA. https://ideone.com/JsVXlp (python)


#7

I think Haskell’s TLE (< 1.01) is too restrictive compared to other languages.
I tested Python3 and C++14 with the same algorithm (as the Editorial) and they pass.
In my attempt of the Haskell codes, I tried Array of List, Sequences, IntSet, and IntMap of Sequences to see all in vain.
Another point of view of unfair TLE for Haskell is that CodeChef configuration does not allow to use Data.Vector which is considered to be the fastest.
I just want to have you consider to either loosen up the TLE for Haskell or to allow Data.Vector library to be used.
Thank you,

  • TJ

#8

please anyone help me
.
.
i am using exactly the same logic but it is wrong answer
.
.

t=int(input())
lis1=list()
dic=dict()
#dic=dict()
#sum=[]
k=0
def maxi(i):
return max(-k,lis1[i-1]+sum(map(maxi,dic[i])))

while t!=0:
n,k=map(int,input().split())
lis1=list(map(int,input().split()))
dic=dict()
for i in range(1,n+1):
dic[i]=[]
for i in range(n-1):
a,b=map(int,input().split())
if a in dic:
dic[a].append(b)
else:
dic[a]=[]
dic[a].append(b)

print(maxi(1))
t=t-1

i have declared list,dictionary and (X) global.
is it wrong ?

#10

I need help please. I used the same logic as the editorialist but I have WA https://www.codechef.com/viewsolution/23964423


#11

Try adding the followings at the top:

import sys
sys.setrecursionlimit(10**5)


#12

Here is my easy to understand ac code,you have to sum the value of nodes of a given subtree and check whether its value is less than -x or not,if it is replace it with -x
//subtree removal
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
vectoradj[100005];
ll a[100005];
ll dp[100005];
ll visited[100005];
ll n,x;

void dfs(ll u)
{
visited[u]=true;
dp[u]=a[u];
ll sum=a[u];
for(ll child : adj[u])
{
if(!visited[child])
{
dfs(child);
sum+=dp[child];
}
}
if(sum<-x)
dp[u]=-x;
else
dp[u]=sum;
}

int main()
{
int t;
cin >> t;
while(t–)
{
cin >> n >> x;
memset(a,0,sizeof(a));
memset(dp,0,sizeof(dp));
memset(visited,false,sizeof(visited));
memset(adj,0,sizeof(adj));
for(int i=1;i<=n;i++)
cin >> a[i];
ll u,v;
for(int i=1;i<=n-1;i++)
{
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1);
cout << dp[1] << endl;
}
return 0;
}


#13

Didn’t check your logic but Why TLE?

Hint:
Argument Passing to Functions
- Pass by Value
- Pass by Reference

#14

Hi,

One thing that is still confusing me is the number of operations ‘k’. Our objective is to minimize the value “X*k” and hence k should only take values 0 or 1 (depending on whether we remove any subtree or not). As per my solution, I found the maximum value of remaining nodes by subtracting each subtree sum from whole tree sum i.e. max(sum(root)- sum[i](for all subtrees)).

I am not able to see any case left in this approach but still getting the wrong answer.
My solution: https://www.codechef.com/viewsolution/23943487


#15

Why we need to add an edge from v to u if we have initialized an edge from u to v already?
If we don’t add an edge from v to u I got wrong answer why is it so? Please explain.


#16

Oh thanks a lot.
I understand now. I used to feel that vectors, like arrays, are sent by reference but instead vectors are sent by value and a copy is generated. Due to recursive nature of function, sending by value leads to TLE. After sending by reference, it works correctly.


#17

Check the Sample Input again.

1
3 5
1 -5 -10
1 2
2 3

#18

still wrong answer
is there any problem in declaring the list and dict global ?


#19

I guess you can’t understand the question.

The question states that you can remove ANY number of subtrees, which are ‘k’ and your profit at the end is the (sum of values of the nodes left in tree - x * k).

You can remove more than one subtree also to maximize the profit. You have to take some test cases and understand that.

Hope this helps :slight_smile:


#20

dats what i have done .
u can check my soln.


#21

How do we know about the count (k) of deletions? I didn’t understand the the mathematical equation?