树状数组(binary indexed tree)

lowbit()运算

非负整数n在二进制下最低位1以及后面的0构成的值
比如lowbit(44)=101100=100=4

求法：对原数按位取反再加一，得到的新数再与原数相与。
比如101100 求反 $\rightarrow$ 010011 再加1 $\rightarrow$ 010100(就是负的原数) 再与101100(44) $\rightarrow$ 100
lowbit(n)=n&(-n)

c++

class Solution {
public:
    map<int,vector<int>>g;
    vector<int> countSubTrees(int n, vector<vector<int>>& edges, string labels) {
        vector<int>ans(n);
        vector<int>visit(n);
        for(int i=0;i<edges.size();i++){
            if(edges[i][1]==0)
                g[edges[i][1]].push_back(edges[i][0]);
            else if(visit[edges[i][1]]==1)
                g[edges[i][1]].push_back(edges[i][0]);
            else
                g[edges[i][0]].push_back(edges[i][1]);
            visit[edges[i][0]]=visit[edges[i][1]]=1;
        }
        for(int i=0;i<n;i++){
            int res=0;
            dfs(i,i,res,labels);
            ans[i]=res+1;
        }
        return ans;
    }
    void dfs(int v,int t,int &res,string labels){
        if(labels[v]==labels[t]&&v!=t)
            res++;
        for(int j=0;j<g[t].size();j++){
            dfs(v,g[t][j],res,labels);
        }
        return;
    }

};