C - And and Pair

题意不说了。简单说下想法
对于每一位二进制位，如果 为 ，那么为了满足 ，可以放 或 有两种放法。对于放 时候，为了满足 ， 只能放 ，对于放 的时候， 能放 或 。所以当 为 时，其对之后的位数贡献为 。
同理，当 为 时，其贡献为 。
这里有个小细节，就是当前 全为 时，也就是说 为 ，那么这个时候， 只能取 ， 可以取 和，但是又要满足 ，所以当在这种情况下，只有一种取法，这种取法也是之前推导贡献情况没有考虑到的，所以最后答案要加 。
也可以开数组预处理幂次，我这里直接快速幂了，时间复杂度
代码如下

#include <iostream>
#include <cstdio>
#include <ctime>
#include <stack>
#include <queue>
#include <map>
#include <cstring>
#include <cstdlib>
#include <set>
#include <string>
#include <vector>
#include <algorithm>
#include <bitset>
#define endl '\n'
#define int long long
#define INF 2147483647
using namespace std;
const int MOD = 1e9+7;
int Max(int a,int b){return a>b?a:b;}
int Min(int a,int b){return a<b?a:b;}
int QPow(int a,int b){int res=1;while(b){if(b&1){res=(res*a)%MOD;}b>>=1;a=(a*a)%MOD;}return res%MOD;}
int Inv(int a,int Mod){return QPow(a,Mod-2);}
int t;
string s;
int ans;
signed main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while(t--){
        cin >> s;
        ans = 0;
        int cnt1 = 0;
        int cnt0 = 0;
        for(int i=s.length()-1;i>=0;i--){
            if(s[i]=='1') {
                ans += 1LL*QPow(2,cnt0)*QPow(3,cnt1);
                ans %= MOD;
            }
            if(s[i]=='1'){
                cnt1++;
            }else{
                cnt0++;
            }
        }
        ans++;
        ans %=MOD;
        cout << ans << endl;
    }
    return 0;
}

K - Tree

树上启发式合并。
我们要找的是什么？找的是点对。我们枚举每个
那么我们是否可以这么考虑，先将第一个孩子的点及其子树的点全部放入桶种（即记录下来），然后其他子树的孩子每次被遍历到一个点就查询在桶种有多少个符合答案的点对。
我们用 来表示某个点的权值以及深度。那么对于这个点，能和其组成一对，且满足条件的点对需满足如下式子
。暴力求法是的，因为要枚举每个点对。
要将其优化为 ，在这里，我们可以用平衡树或者权值线段树(动态开点)来做。权值线段树维护深度为 范围内权值为 的点有多少个。需要注意的是整棵树的最大深度为 ，即退化为链。所以还需要满足以下条件

总时间复杂度
代码如下:

#include <iostream>
#include <cstdio>
#include <ctime>
#include <stack>
#include <queue>
#include <map>
#include <cstring>
#include <cstdlib>
#include <set>
#include <string>
#include <vector>
#include <algorithm>
#include <bitset>
#define endl '\n'
#define int long long
#define INF 2147483647
#define MOD 19260817
using namespace std;
int Max(int a,int b){return a>b?a:b;}
int Min(int a,int b){return a<b?a:b;}
int QPow(int a,int b){int res=1;while(b){if(b&1){res=(res*a)%MOD;}b>>=1;a=(a*a)%MOD;}return res%MOD;}
int Inv(int a,int Mod){return QPow(a,Mod-2);}
const int MAXN = 1e5+10;
// struct Edge{
//     int v,next;
// }e[MAXN*2];
vector<int> E[MAXN];
int ecnt;int head[MAXN];
int res;
int root[MAXN],ls[MAXN*100],rs[MAXN*100],num[MAXN*100],cnt;
void update(int &p,int l,int r,int x,int v){
    if(!p) p = ++cnt;
    num[p] += v;
    if(l==r) return;
    int mid = (l+r)>>1;
    if(x<=mid) update(ls[p],l,mid,x,v);
    else update(rs[p],mid+1,r,x,v);
}
int ask(int p,int l,int r,int ql,int qr){
    if(!p) return 0;
    if(ql > qr) return 0;
    if(ql <= l && qr >= r){
        return num[p];
    }
    int ans = 0;
    int mid = (l+r)>>1;
    if(ql <= mid){
        ans += ask(ls[p],l,mid,ql,qr);
    }
    if(qr > mid){
        ans += ask(rs[p],mid+1,r,ql,qr);
    }
    return ans;
}
int n,k,w[MAXN],fa[MAXN];
int dep[MAXN];
int siz[MAXN];
int st[MAXN],ed[MAXN],dfn[MAXN],tot;
void dfs(int u){
    siz[u] = 1;
    st[u] = ++tot;
    dfn[tot] = u;
    for(int v:E[u]){
        if(v != fa[u]){
            dep[v] = dep[u] + 1;
            dfs(v);
            siz[u] += siz[v];
        }
    }
    ed[u] = tot;
}
void dfs(int u,bool keep){
    int mx = -1;
    int son = -1;
    for(int v:E[u]){
        if(v != fa[u] && siz[v] > mx){
            mx = siz[v];
            son = v;
        }
    }
    for(int v:E[u]){
        if(v != fa[u] && v != son){
            dfs(v,0);
        }
    }
    if(son != -1){
        dfs(son,1);
    }
    for(int v:E[u]){
        if(v != fa[u] && v != son){
            for(int i = st[v];i <= ed[v];i++){
                int x = dfn[i];
                int need = 2*w[u]-w[x];
                if(need >= 0 && need <= n){
                    res+=ask(root[need],1,n,dep[u]+1,Min(n,2*dep[u]+k-dep[x]));
                }
            }
            for(int i=st[v];i <= ed[v];i++){
                int x = dfn[i];
                update(root[w[x]],1,n,dep[x],1);
            }
        }
    }
    update(root[w[u]],1,n,dep[u],1);
    if(!keep){
        for(int i=st[u];i <= ed[u];i++){
            int x = dfn[i];
            update(root[w[x]],1,n,dep[x],-1);
        }
    }
}
signed main(void){
    // cin >> n >> k;
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%lld",w+i);
        // cin >> w[i];
    }
    for(int i=2;i<=n;i++){
        scanf("%lld",fa+i);
        // cin >> fa[i];
        E[fa[i]].push_back(i);
    }
    dfs(1);
    dfs(1,0);
    printf("%lld",2LL*res);
    return 0;
}