D - Range = √Sum 构造,F - Strange Memory 树上启发式合并

D - Range = √Sum 构造

当n为偶数的时候可以让将n划分为n/2个组，让每一个组的两个数和为2*n,这样n个数的和就是n^2,所以只需要让最大值和最小值差为n就可以了，那就从首部和尾部分别开始构造，前一半是n-n/2,n-n/2+1,,,;后一半是n+n/2,n+n/2-1,,,;

当n为奇数的话，考虑将n这个值作为数组的中间元素，然后让数组中的数公差为1的来构造，这样最大值和最小值差为n-1,这样构造出来的和为n^2,然后再将整个数组+2，和就为n^2+2*n,然后将最大值+1，最小值-1，最大值与最小值的差值为n+1,为了让和为n^2+2*n+1,还需要让倒数第二个数+1，这是合法的，因为前一步已经让最大值+1了，所以不会有相同的数

Codeforces Round #836 (Div. 2) Editorial - Codeforces

#include
//#pragma-GCC-optimize("-Ofast");
#define int long long
#define ll __int128
#define lowbit(x) ((x)&(-x))
#define endl '\n'
#define pause system("pause")
using namespace std;
const int N=2e6+5;
const int mod=1e9+7;
const int inf=1e18;
const int up=1e6;
const double pi=acos(-1);
int qpow(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int getinv(int a){return qpow(a,mod-2);}
int t,n,ans[N];
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--)
    {
        cin>>n;
        if(n&1)
        {
            ans[n/2+1]=n;
            int cnt=1;
            for(int i=n/2;i>=1;i--) ans[i]=n-cnt++;
            cnt=1;
            for(int i=n/2+2;i<=n;i++) ans[i]=n+cnt++;
            for(int i=1;i<=n;i++) ans[i]+=2;
            ans[1]--;ans[n]++;ans[n-1]++;
        }
        else
        {
            ans[1]=n-n/2;ans[n]=n+n/2;
            int cnt=1;
            for(int i=2;i<=n/2;i++) ans[i]=n-n/2+cnt++;
            cnt=1;
            for(int i=n-1;i>n/2;i--) ans[i]=n+n/2-cnt++;
        }
        for(int i=1;i<=n;i++) cout<" ";
        cout<
    }
    return 0;
}
 

F - Strange Memory 树上启发式合并

结论：两个数的异或等于这两个数的二进制按位异或再加起来

比如 1101^1001=1 000^ 1000+100^000+00^00+1^1;

可以发现对于u和u的祖宗是不会满足条件的，即满足条件的是一定是u和另外子树的点，所以我们可以一个子树一个子树的来算，算完一个子树就将这个子树的信息统计下来，开一个num[a[u]][i][0/1]的数组，表示a[u]的第i位是0或是1的有多少个，算一个点u就可以把u拆成二进制将按位来算最后加起来就可以，对于子树信息的统计用启发式合并就可以了

F. Strange Memory__7许的博客-CSDN博客

#include
//#pragma-GCC-optimize("-Ofast");
//#define int long long
#define ll long long
#define lowbit(x) ((x)&(-x))
#define endl '\n'
#define pause system("pause")
using namespace std;
const int N=2e5+5;
const int mod=1e9+7;
const int inf=1e18;
const int up=1e6;
const double pi=acos(-1);
int qpow(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int getinv(int a){return qpow(a,mod-2);}
int head[N],cnt;
struct Edge
{
    int next,to;
}e[N];
void addedge(int from,int to)
{
    e[++cnt].next=head[from];
    e[cnt].to=to;
    head[from]=cnt;
}
const ll maxu=(1<<20);
int n,son[N],num[maxu][21][2],siz[N],fson,a[N];
ll ans;
vector<int>g;
void dfs(int u,int fa)
{
    siz[u]=1;
    for(int i=head[u];i;i=e[i].next)
    {
        int j=e[i].to;
        if(j==fa) continue;
        dfs(j,u);
        siz[u]+=siz[j];
        if(siz[j]>siz[son[u]]) son[u]=j;
    }
}
void add(int u,int val)
{
    for(int i=0;i<=20;i++)
    {
        num[a[u]][i][(u>>i)&1]+=val;
    }
}
void del(int u,int fa)
{
    for(int i=head[u];i;i=e[i].next)
    {
        int j=e[i].to;
        if(j==fa) continue;
        del(j,u);
    }
    add(u,-1);
}
int query(int u,int val)
{
    int res=0;
    for(int i=0;i<=20;i++)
    {
        int bit=!((u>>i)&1);
        res+=num[val][i][bit]*(1LL<
    }
    return res;
}
void cal(int u,int fa,int lca)
{
    g.push_back(u);
    ans+=query(u,a[u]^a[lca]);
    for(int i=head[u];i;i=e[i].next)
    {
        int j=e[i].to;
        if(j==fa||j==fson) continue;
        cal(j,u,lca);
    }
}
void dsu(int u,int fa,int keep)
{
    for(int i=head[u];i;i=e[i].next)
    {
        int j=e[i].to;
        if(j!=fa&&j!=son[u]) dsu(j,u,0);
    }
    if(son[u]) dsu(son[u],u,1),fson=son[u];
    for(int i=head[u];i;i=e[i].next)//把根节点当作lca去算子树中的每一个点
    {
        int j=e[i].to;
        if(j==fa||j==fson) continue;
        cal(j,u,u);
        for(auto x:g)
            add(x,1);
        g.clear();
    }
    add(u,1);
    fson=0;
    if(!keep) del(u,fa);
}
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i
    {
        int u,v;cin>>u>>v;
        addedge(u,v);
        addedge(v,u);
    }
    dfs(1,0);
    dsu(1,0,1);
    cout<
    return 0;
}