UVa 1354 Mobile Computing

乍一看似乎无从下手，但仔细一想就发现其实就是枚举二叉树的形态，然后计算贡献。

用二进制表示二叉树，预处理出所有可能的子树（子集）的贡献。在搜索时以左子树作为变量，不断除去左子树二进制表示中的 1。分别递归搜索左、右子树后，遍历左、右子树可能的贡献（存在一个vector里），从而算出宽度。

这么说起来过于抽象了，来看看有详细注释的代码吧。

（图1 ↓）

#include
#include
#include
#include
#include
using namespace std;
struct TREE {double L,R; TREE():L(0),R(0) {};}; // L, R 表示的是当节点的根向左和向右能到达的最远距离
vectortree[1<<7];
double r;int s,vis[1<<7]; // vis[] 记录这个子树是否被 dfs 过了
double w[1<<7],sum[1<<7];
void dfs(int subset)
{
    if(vis[subset])return;
    vis[subset]=1;
    int flag=0; // 如果没有子树，那么要在之后加上一个空节点，以便于计算贡献
    for(int left=subset&(subset-1);left;left=subset&(left-1)) // 技巧：subset&(left-1)得到的就是left除去最低的一个1之后的结果
    {
        flag=1;
        int right=left^subset; // 异或操作取的是左子树集合的补集，也就是右子树
        dfs(left);dfs(right);
        double dL=sum[right]/sum[subset],dR=1-dL; // 这里 dL 为什么是右子树大小除以总大小呢？可以结合 F1×l1=F2×l2 理解：若F1>F2，则l1