There are $2^{n}$ teams. There is only one person in each team at first. Every teams' score is $0$ at first. They play a tournament game. If team $A$ and team $B$ fights, team that has more team members wins. (If number of team members are equal, any team can win.) Number of members in losing team is the score that winner team earns.
Also, loser team writes their final score at the board, and every member of loser team becomes member of winner team. When all the tournament game ended, final winner team also writes their final score at the board. Say the sum of all numbers in the board is $M$. I want to figure out the maximum value of $M$. If the tournament tree is full binary tree, $M=n \cdot 2^{n-1}$. I also know that this problem can be interpreted into "Finding the worst case time complexity of linked list representation of disjoint sets" so $O(n \cdot 2^{n})$. I think $M=n \cdot 2^{n-1}$ is the maximum value, but I have trouble proving it. Can someone help?
At any particular time, let $S$ be the total score of all teams - either the now-constant score of losing teams, or the still changing score of winning teams. And let $L$ be the sum of the losses each player (not team) has racked up. At the start of the tournament, both values are $0$.
If a team with current score $S_1$ defeats another team with $m$ members and s current score of $S_2$, then $S_2$ remains unchanged while $S_1$ increases by $m$. So the total score $S$ increases by $m$. But the $m$ members of the losing team each add $1$ to their loss total. So the total number of losses also goes up by $m$. Thus at all times $S = L$.
Notice that in this tournament, every pair of players $a$ and $b$ are on opposing teams exactly once. Each such pairing involves one loss, but those losses are not unique. If player $b$ loses a match, that loss counts but once, while it settles all pairings between $b$ and members of the winning team. So to maximize the total number of losses, we need to minimize the number of pairings that are removed by a game - that is, the size of the winning team. Since the winning team has to be at least as big as the losing team, the number of losses is maximized when all competitions are between teams as close as possible to the same size.
When the total number of players is a power of $2$, it is possible to assure that all matches are between teams of the same size, thus maximizing losses, and total score. As you've calculated, this is $n2^{n-1}$