Niuke multi School Game 3 A, c+ weight segment tree

await a vacancy or job opening ：H,J

A topic
Knowledge point ：dfs order ,LCA nature

The question ： Given two trees a and b, Every tree n Nodes , Each node has its own weight . Regulations n There are k Key points （k At least for 2 At most n）, Can you ignore one a Trees and b Key nodes with the same number in the tree , Make the remaining key nodes of the two trees lca Satisfy ： stay a In the tree lca The weight of should be greater than b In number lca A weight . If possible , Please output the number of feasible schemes .

Ideas ：
nature 1： Of several nodes in a tree lca Among these points dfs Of the smallest and largest nodes of the order lca.

That's easy to do . We write about two trees respectively lca, about k The key nodes ignore enumeration respectively and make the answer

PS： Write encapsulated code for the first time , Two trees lca True cancer , It's impossible to do this problem without knowing the nature ,ex pinch , And the enumerated points can be up to n individual , It's likely to double lca 了 , Only tree section lca+lca nature +dfs I'm going to do it .

#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct node
{
    
    int nex,to;
};
const int N=5e5+10;
int key[N],a[N],b[N],keyy[100005];
struct tree
{
    
node edge[N<<1],edge2[N<<1];
int dep[N],head[N],tot,fa[N],top[N],son[N],siz[N],dfsorder[N],cnt,dfn[N];
void add(int from,int to)
{
    
    edge[++tot].nex=head[from];
    edge[tot].to=to;
    head[from]=tot;
}
void DFS1(int now,int fath)
{
    
    if(key[now]) dfsorder[++cnt]=now,dfn[now]=cnt;
    fa[now]=fath;
    siz[now]=1;son[now]=0;
    dep[now]=dep[fath]+1;
    for(int i=head[now];i;i=edge[i].nex){
    
        if(edge[i].to==fath)
            continue;
        DFS1(edge[i].to,now);
        siz[now]+=siz[edge[i].to];
        if(siz[son[now]]<siz[edge[i].to])
            son[now]=edge[i].to;
    }
}
void DFS2(int now,int topx)//topx, Pay more attention to your son than to your son 
{
    
    top[now]=topx;
    if(son[now])
    {
    
        DFS2(son[now],topx);
    }
    else
        return ;
    for(int i=head[now];i;i=edge[i].nex)
    {
    
        if(edge[i].to!=fa[now]&&edge[i].to!=son[now])
        {
    
            DFS2(edge[i].to,edge[i].to);
        }
    }
}

int LCA(int x,int y)
{
    
    while(top[x]!=top[y])
    {
    
        if(dep[top[x]]<dep[top[y]])
        {
    
            swap(x,y);
        }
        x=fa[top[x]];
    }
    return dep[x]<dep[y]?x:y;
}

}t1,t2;

int main()
{
    
    int n,k;
    cin>>n>>k;
    for(int i=1,temp;i<=k;i++)
    {
    
        cin>>temp;key[temp]=i;keyy[i]=temp;
    }
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=2,p;i<=n;i++)
    {
    
        cin>>p;t1.add(i,p);t1.add(p,i);
    }
    for(int i=1;i<=n;i++)
        cin>>b[i];
    for(int i=2,p;i<=n;i++)
    {
    
        cin>>p;t2.add(i,p);t2.add(p,i);
    }
    t1.DFS1(1,0);t1.DFS2(1,1);//t1.DFS3(1,0);
    t2.DFS1(1,0);t2.DFS2(1,1);//t2.DFS3(1,0);
    ll la,lb,ans=0;
    for(int i=1;i<=k;i++){
    
        if(t1.dfn[keyy[i]]==1) la=t1.LCA(t1.dfsorder[2],t1.dfsorder[k]);
        else if(t1.dfn[keyy[i]]==k) la=t1.LCA(t1.dfsorder[1],t1.dfsorder[k-1]);
        else la=t1.LCA(t1.dfsorder[1],t1.dfsorder[k]);
        if(t2.dfn[keyy[i]]==1) lb=t2.LCA(t2.dfsorder[2],t2.dfsorder[k]);
        else if(t2.dfn[keyy[i]]==k) lb=t2.LCA(t2.dfsorder[1],t2.dfsorder[k-1]);
        else lb=t2.LCA(t2.dfsorder[1],t2.dfsorder[k]);
        if(a[la]>b[lb]) ans++;
    }
    printf("%lld\n",ans);
	return 0;
}

C
String sort .

Although it's string sorting , But there are several options .

The most dangerous one ： Card line pass , But I can only blame myself

#include <iostream>
#include <algorithm>
const int N = 2e6+100;
std::string s[N];
bool cmp(const std::string &a,const std::string &b)
{
    
    std::string s1=a+b;
    std::string s2=b+a;
    return s1<s2;
}
int main()
{
    
    std::cin.tie(0);
    std::cout.tie(0);
    std::ios::sync_with_stdio(0);
    int n;
    std::cin>>n;
    for(int i=1;i<=n;i++)
    {
    
        std::cin>>s[i];
    }
    std::sort(s+1,s+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
    
        std::cout<<s[i];
    }
    //cout<<endl;

    return 0;
}

another ： In spite of the violence , But I have pruning

This kind of code should be a positive solution , ran 1 Seconds and more , Less than the time limit 1/3

#include<bits/stdc++.h>
using namespace std;
char ch[20000005];
string a[2000005];
int cnt,nl,ml;
bool cmp(string &n,string &m)
{
    
	int minn=min(n.length()-1,m.length()-1);
	if(n.length()==m.length())
        return n<m;
    for(int i=0;i<=minn;i++)
		if(n[i]!=m[i])
            return n[i]<m[i];
    return n+m<m+n;
}
int main()
{
    
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	    cin>>a[i];
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)
	    cout<<a[i];
	return 0;
}

Weight line tree .
The line segment tree is about to split , But I found that I forgot to pinch my weight segment tree . So do it .

Pre knowledge ： Base line tree （ with great facility ）, discretization （ Master operation ）.

Main use ： It is mainly used to record the number of occurrences of a certain interval , For example, given an array , We insert , We can get the number of occurrences of an element in a certain interval in this array .
example ： Tree query interval K Big value , The first k Small value , How many times does a certain number appear in an interval

#include <iostream>
#define ls p<<1
#define rs p<<1|1
#define mid ((l+r)/2)
using namespace std;

const int N = 1e5+100;

int tree[N<<2],tag[N<<2];

int query_max(int p,int l,int r,int k)
{
    
    if(k<=0)
        return 0;
    if(l==r)
        return l;
    int right=tree[rs];
    if(k<=right)
        return query_max(rs,mid+1,r,k);
    else
        return query_max(ls,l,mid,k-right);
}
int query_min(int p,int l,int r,int k)
{
    
    if(k<=0)
        return 0;
    if(l==r){
    
        return l;
    }
    int left=tree[ls];
    if(k<=left)
        return query_min(ls,l,mid,k-left);
    else
        return query_min(rs,mid+1,r,k);
}
int query_num(int l,int r,int p,int x)
{
    
    if(l==r)
        return tree[p];
    else{
    
        if(x<=mid)
            return query_num(l,mid,ls,x);
        else
            return query_num(mid+1,r,rs,x);
    }
}
void fix(int l,int r,int p,int x)
{
    
    if(l==r){
    
        tree[p]++;
        return ;
    }
    if(x<=mid)
        fix(l,mid,ls,x);
    if(x>mid)
        fix(mid+1,r,rs,x);
    tree[p]=tree[ls]+tree[rs];
}