#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define MD (1000000007U)
template < class S, class T> inline S chmax( S & a, T b) {
if ( a< b) {
a= b;
}
return a;
}
#define main dummy_main
int main( ) {
return 0 ;
}
#undef main
#define TreeNode dummy_TreeNode
struct TreeNode{
}
;
#undef TreeNode
int sz;
int s[ 100000 ] ;
int getsum( TreeNode * root) {
if ( root== NULL ) {
return 0 ;
}
int res = root- > val + getsum( root- > left) + getsum( root- > right) ;
s[ sz++ ] = res;
return res;
}
class Solution{
public :
int maxProduct( TreeNode* root) {
int i;
long long all;
long long res = 0 ;
sz = 0 ;
all = getsum( root) ;
for ( i= ( 0 ) ; i< ( sz) ; i++ ) {
chmax( res, s[ i] * ( all - s[ i] ) ) ;
}
return res % MD;
}
}
;
// cLay varsion 20200214-1
// --- original code ---
// #define main dummy_main
// {}
// #undef main
//
// #define TreeNode dummy_TreeNode
// struct TreeNode {};
// #undef TreeNode
//
// int sz, s[1d5];
//
// int getsum(TreeNode *root){
// if(root==NULL) return 0;
// int res = root->val + getsum(root->left) + getsum(root->right);
// s[sz++] = res;
// return res;
// }
//
// class Solution {
// public:
// int maxProduct(TreeNode* root) {
// ll all, res = 0;
// sz = 0;
// all = getsum(root);
// rep(i,sz) res >?= s[i] * (all - s[i]);
// return res % MD;
// }
// };
I3ByYWdtYSBHQ0Mgb3B0aW1pemUgKCJPZmFzdCIpCiNpbmNsdWRlPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgTUQgKDEwMDAwMDAwMDdVKQp0ZW1wbGF0ZTxjbGFzcyBTLCBjbGFzcyBUPiBpbmxpbmUgUyBjaG1heChTICZhLCBUIGIpewogIGlmKGE8Yil7CiAgICBhPWI7CiAgfQogIHJldHVybiBhOwp9CiNkZWZpbmUgbWFpbiBkdW1teV9tYWluCmludCBtYWluKCl7CiAgcmV0dXJuIDA7Cn0KI3VuZGVmIG1haW4KI2RlZmluZSBUcmVlTm9kZSBkdW1teV9UcmVlTm9kZQpzdHJ1Y3QgVHJlZU5vZGV7Cn0KOwojdW5kZWYgVHJlZU5vZGUKaW50IHN6OwppbnQgc1sxMDAwMDBdOwppbnQgZ2V0c3VtKFRyZWVOb2RlICpyb290KXsKICBpZihyb290PT1OVUxMKXsKICAgIHJldHVybiAwOwogIH0KICBpbnQgcmVzID0gcm9vdC0+dmFsICsgZ2V0c3VtKHJvb3QtPmxlZnQpICsgIGdldHN1bShyb290LT5yaWdodCk7CiAgc1tzeisrXSA9IHJlczsKICByZXR1cm4gcmVzOwp9CmNsYXNzIFNvbHV0aW9uewogIHB1YmxpYzoKICBpbnQgbWF4UHJvZHVjdChUcmVlTm9kZSogcm9vdCl7CiAgICBpbnQgaTsKICAgIGxvbmcgbG9uZyBhbGw7CiAgICBsb25nIGxvbmcgcmVzID0gMDsKICAgIHN6ID0gMDsKICAgIGFsbCA9IGdldHN1bShyb290KTsKICAgIGZvcihpPSgwKTtpPChzeik7aSsrKXsKICAgICAgY2htYXgocmVzLCBzW2ldICogKGFsbCAtIHNbaV0pKTsKICAgIH0KICAgIHJldHVybiByZXMgJSBNRDsKICB9Cn0KOwovLyBjTGF5IHZhcnNpb24gMjAyMDAyMTQtMQoKLy8gLS0tIG9yaWdpbmFsIGNvZGUgLS0tCi8vICNkZWZpbmUgbWFpbiBkdW1teV9tYWluCi8vIHt9Ci8vICN1bmRlZiBtYWluCi8vIAovLyAjZGVmaW5lIFRyZWVOb2RlIGR1bW15X1RyZWVOb2RlCi8vIHN0cnVjdCBUcmVlTm9kZSB7fTsKLy8gI3VuZGVmIFRyZWVOb2RlCi8vIAovLyBpbnQgc3osIHNbMWQ1XTsKLy8gCi8vIGludCBnZXRzdW0oVHJlZU5vZGUgKnJvb3QpewovLyAgIGlmKHJvb3Q9PU5VTEwpIHJldHVybiAwOwovLyAgIGludCByZXMgPSByb290LT52YWwgKyBnZXRzdW0ocm9vdC0+bGVmdCkgKyAgZ2V0c3VtKHJvb3QtPnJpZ2h0KTsKLy8gICBzW3N6KytdID0gcmVzOwovLyAgIHJldHVybiByZXM7Ci8vIH0KLy8gCi8vIGNsYXNzIFNvbHV0aW9uIHsKLy8gcHVibGljOgovLyAgIGludCBtYXhQcm9kdWN0KFRyZWVOb2RlKiByb290KSB7Ci8vICAgICBsbCBhbGwsIHJlcyA9IDA7Ci8vICAgICBzeiA9IDA7Ci8vICAgICBhbGwgPSBnZXRzdW0ocm9vdCk7Ci8vICAgICByZXAoaSxzeikgcmVzID4/PSBzW2ldICogKGFsbCAtIHNbaV0pOwovLyAgICAgcmV0dXJuIHJlcyAlIE1EOwovLyAgIH0KLy8gfTsK