C~F Java题解，代码已去除冗余~~~

C 小红走网格

首先在任意方向上不管怎么走，坐标距离0都必定是步长最大公约数的倍数，因此分别验证即可，时间复杂度(Tlog((max(a,b,c,d)))

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        for(int i=0;i<t;i++){
            int x=sc.nextInt(),y=sc.nextInt(),a=sc.nextInt(),b=sc.nextInt(),c=sc.nextInt(),d=sc.nextInt();
            System.out.println(y%gcd(a,b)+x%gcd(c,d)==0?"YES":"NO");
        }
    }
    static int gcd(int a,int b){
        return a<b?gcd(b,a):b==0?a:gcd(a%b,b);
    }
}

D 隐匿社交网络

两个数与运算是正数，那么这两个数必须在至少一个比特位上都是1，因此把某一位是1的所有数，分配在同一个连通块即可，并查集实现，时间复杂度O(Tα(n)logC)，其中C==1e18

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        for(int i=0;i<t;i++){
            int n=sc.nextInt(),group[]=new int[n],count[]=new int[n],ans=0;
            List<Integer> list[]=new List[66];
            for(int j=0;j<66;j++){
                list[j]=new ArrayList<>();
            }
            for(int j=0;j<n;j++){
                count[j]=1;
                group[j]=j;
                long w=sc.nextLong();
                for(int k=0;k<66;k++){
                    if((w>>k&1)==1){
                        list[k].add(j);
                    }
                }
            }
            for(List<Integer> l:list){
                for(int j=1;j<l.size();j++){
                    union(l.get(j),l.get(j-1),group,count);
                }
            }
            for(int a:count){
                ans=Math.max(ans,a);
            }
            System.out.println(ans);
        }
    }
    static void union(int a,int b,int group[],int count[]){
        int p1=find(a,group),p2=find(b,group);
        if(p1!=p2){
            count[p1]+=count[p2];
            group[p2]=p1;
        }
    }
    static int find(int a,int group[]){
        return a==group[a]?a:(group[a]=find(group[a],group));
    }
}

E 1or0

正难则反，一个区间内如果没有0，那么这个区间的与运算全部是0，那么只需要维护任意区间数字的连续0区间情况，再用全1的和减去0的贡献，可用线段树维护每个区间的0贡献，以及该区间的左右最大连续0个数，以便于在再去加合并的时候进行计算，事假复杂度O((n+q)logn)

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String args[]) throws IOException{
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        int n=Integer.parseInt(bf.readLine());
        String s=bf.readLine();
        SegTree st=new SegTree(0,n-1);
        build(st,s);
        for(int i=Integer.parseInt(bf.readLine());i!=0;i--){
            StringTokenizer sto=new StringTokenizer(bf.readLine());
            int l=Integer.parseInt(sto.nextToken())-1,r=Integer.parseInt(sto.nextToken())-1;
            bw.write((long)(r-l+1)*(r-l+2)/2-find(st,l,r)[0]+"\n");
        }
        bw.flush();
    }
    static long[] find(SegTree st,int a,int b){
        int l=st.l,r=st.r;
        if(l==a&&r==b){
            return new long[]{st.sum,st.lmax,st.rmax};
        }
        int mid=(l+r)>>1;
        if(b<=mid){
            return find(st.left,a,b);
        }
        if(a>mid){
            return find(st.right,a,b);
        }
        long arr1[]=find(st.left,a,mid),arr2[]=find(st.right,mid+1,b);
        return new long[]{arr1[0]+arr2[0]+arr1[2]*arr2[1],arr1[1]==mid-a+1?arr2[1]+mid-a+1:arr1[1],arr2[2]==b-mid?arr1[2]+b-mid:arr2[2]};
    }
    static void build(SegTree st,String s){
        int l=st.l,r=st.r;
        if(l==r){
            st.sum=st.lmax=st.rmax=(s.charAt(l)-'0')^1;
        }
        else{
            int mid=(l+r)>>1;
            st.left=new SegTree(l,mid);
            st.right=new SegTree(mid+1,r);
            build(st.left,s);
            build(st.right,s);
            st.sum=st.left.sum+st.right.sum+st.left.rmax*st.right.lmax;
            st.lmax=st.left.lmax==mid-l+1?st.right.lmax+mid-l+1:st.left.lmax;
            st.rmax=st.right.rmax==r-mid?st.left.rmax+r-mid:st.right.rmax;
        }
    }
}
class SegTree{
    int l,r;
    long sum,lmax,rmax;
    SegTree left,right;
    SegTree(int l,int r){
        this.l=l;
        this.r=r;
    }
}

F 计树

对于每个节点p下的待考虑节点个数sum，共有sum^2中配对方式，其中它们的LCA不会一定在p所在的子树中，而通过深搜可以算出以p的子孙节点为LCA的点对儿数量，因此，p点的数据也可以求得，也就是剩下的可配对儿数量，时间复杂度O(n)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        List<Integer> path[]=new List[n+5];
        for(int i=1;i<=n;i++){
            path[i]=new ArrayList<>();
        }
        for(int i=0;i<n-1;i++){
            int u=sc.nextInt(),v=sc.nextInt();
            path[u].add(v);
            path[v].add(u);
        }
        long ans[]=new long[n+5];
        boolean has[]=new boolean[n+5];
        for(int i=sc.nextInt();i!=0;i--){
            has[sc.nextInt()]=true;
        }
        find(1,0,path,ans,has);
        for(int i=1;i<=n;i++){
            System.out.print(ans[i]+" ");
        }
    }
    static int find(int k,int p,List<Integer> path[],long ans[],boolean has[]){
        int count=0;
        for(int a:path[k]){
            if(a!=p){
                int cur=find(a,k,path,ans,has);
                ans[k]-=(long)cur*cur;
                count+=cur;
            }
        }
        if(has[k]){
            count++;
        }
        ans[k]+=(long)count*count;
        return count;
    }
}