首页 > 其他分享 >ucup hefei 题解

ucup hefei 题解

时间：2023-12-06 18:44:05浏览次数：40  
标签：ch int 题解 hefei seg long FF ucup define

比赛链接

B

很有意思的题
首先题目的要求为可以拆分成 \(2\) 个不相交的不降子序列
根据 \(dilworth\) 定理，最小链覆盖 \(=\) 最长反链，所以要求最长反链 \(\le 2\)
即原序列的逆序列的最长不降子序列长度 \(\le 2\)

不难得到一个 \(dp\) 做法为：
令 \(f_{i,j}\) 为到数 \(i\)，最长上升子序列长度为 \(j\) 的方案数
我们考虑从小到大加数（已经变成了逆序列）
可以发现，第一个数前面的一段是不会影响 \(lis\) 长度的，不妨枚举其长度，对于最前面的一个加数区间，后面的序列是要舍弃的，所以需要枚举第一个加数区间
上面的转移建议自己想，不难

时间复杂度 \(O(n^3)\)

这道题目的关键在于：转化为流问题，用 \(dilworth\)，得到求逆序列 \(lis\) 长度 \(\le 2\) 的序列个数

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
    FF=0;int RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    FF*=RR;
}
const int N=510,P=998244353;
int n,a[N],f[N][N],C[N][N];
inline void inc(int &x,int y){ x+=y;if(x>=P) x-=P;}
int main(){
    read(n);
    C[0][0]=1;
    F(i,1,N-1) F(j,0,i) C[i][j]=(!j||i==j)?1:(C[i-1][j-1]+C[i-1][j])%P;
    F(i,1,n) read(a[n-i+1]);
    int res=0;
    f[0][0]=1;
    F(i,1,n){
        if(!a[i]){ F(j,0,res) f[i][j]=f[i-1][j];continue;}
        F(j,0,res){
            F(k,1,j){
                int le=j-k+1;
                F(t,0,a[i]-1) inc(f[i][k+t],1ll*f[i-1][j]*C[a[i]-1-t+le-1][a[i]-1-t]%P);
            }
            inc(f[i][j+a[i]],f[i-1][j]);
        }
        res+=a[i];
    }
    int ans=0;
    F(i,1,res) inc(ans,f[n][i]);
    printf("%d\n",ans);
    return 0;
}

C

\(PAM\) 板子题
没学过 \(PAM\)，现场贺了一份板子上去
一个技巧是倍长字符串，但也比较套路了
时间复杂度 \(O(n)\)

#include <bits/stdc++.h>
using namespace std;
const int N=6e6+100,P=998244353;
char str[N];
int n,s[N],res[N];
int p,q,fail[N],cnt[N],len[N],tot,last,ch[N][10];
inline int newnode(int x){
    len[++tot]=x;return tot;
}
inline int getfail(int x,int n){
    while(s[n-len[x]-1]!=s[n]) x=fail[x];
    return x;
}
inline int read(){
    int FF=0,RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    return FF*RR;
}
void work(int neg){
    for(int i=0;i<=n;i++){
        cnt[i]=fail[i]=len[i]=0;
        for(int j=0;j<=9;j++) ch[i][j]=0;
    }
    p=0,q=0;
    s[0]=-1,fail[0]=1,last=0;
    len[0]=0,len[1]=-1,tot=1;
    for(int i=1;i<=n;i++){
        p=getfail(last,i);
        if(!ch[p][s[i]]){
            q=newnode(len[p]+2);
            fail[q]=ch[getfail(fail[p],i)][s[i]];
            ch[p][s[i]]=q;
        }
        ++cnt[last=ch[p][s[i]]];
    }
    for(int i=tot;i;--i) cnt[fail[i]]+=cnt[i];
    for(int i=1;i<=tot;i++) res[i]+=cnt[i]*neg;
}
int main(){
    n=read();
    scanf("%s",str+1);
    for(int i=1;i<=n;i++) s[i]=str[i]-'0';
    work(-1);
    for(int i=1;i<=n;i++) s[i+n]=s[i];
    n<<=1;work(1);
    int ans=0;
    for(int i=1;i<=tot;i++) if(len[i]<=n/2)
        ans=(ans+1ll*len[i]*res[i]%P*res[i])%P;
    printf("%d\n",ans);
    return 0;
}

D

枚举 \(i\) 之后题目变得很不可做
考虑换个角度，枚举 \(k\)
不难发现，合法的 \(i\) 是一个前缀
不妨二分 \(i\)，判断合法直接字符串哈希看：\(hash[1,mid-2k]+hash[2k+1,mid]=2hash[2k+1,mid-2k]\)

时间复杂度 \(O(n\log n)\)

这道题的关键在于想到枚举 \(k\) 和哈希

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
    int FF=0,RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    return FF*RR;
}
const int N=2000100;
int n,tag[N],a[N],base[6];
int gtnum(char x){
    if('0'<=x&&x<='9') return x-'0';
    if('a'<=x&&x<='z') return 10+x-'a';
    if('A'<=x&&x<='Z') return 36+x-'A';
}
struct Hash{
    int base,mod,p[N],h[N];
    void build(){
        p[0]=1;
        F(i,1,n) p[i]=1ll*p[i-1]*base%mod;
        F(i,1,n) h[i]=(1ll*h[i-1]*base+a[i])%mod;
    }
    int gethash(int l,int r){ return (h[r]-1ll*h[l-1]*p[r-l+1]%mod+mod)%mod;}
}hash1,hash2;
int main(){
    n=read();
    base[0]=1;
    F(i,1,4) base[i]=base[i-1]*62;
    F(i,1,n){
        string s;cin>>s;
        DF(j,SZ(s),0) a[i]+=base[SZ(s)-j]*gtnum(s[j]);
    }
    hash1.base=31,hash1.mod=1e9+7,hash2.base=131,hash2.mod=998244353;
    hash1.build(),hash2.build();
    F(k,1,n/2){
        int l=k*2,r=n+1;
        while(l<r-1){
            int mid=(l+r)>>1;
            if((hash1.gethash(1,mid-2*k)+hash1.gethash(2*k+1,mid))%hash1.mod==hash1.gethash(k+1,mid-k)*2%hash1.mod
             &&(hash2.gethash(1,mid-2*k)+hash2.gethash(2*k+1,mid))%hash2.mod==hash2.gethash(k+1,mid-k)*2%hash2.mod) l=mid;
            else r=mid;
        }
        tag[k*2+1]++,tag[l+1]--;
    }
    F(i,1,n) tag[i]+=tag[i-1],putchar((tag[i]>0)+48);
    return 0;
}

E

签到题，发现 \(x\) 轴和 \(y\) 轴互不影响
直接对于 \(x\) 轴和 \(y\) 轴分别跑一遍一维距离统计即可
时间复杂度 \(O(n)\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
    int FF=0,RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    return FF*RR;
}
const int N=1100;
int n,m,a[N][N],disc[N*N];
LL s1[N*N],s2[N*N];
signed main(){
    n=read(),m=read();
    LL ans=0;
    int cnt=0;
    F(i,1,n) F(j,1,m) a[i][j]=read(),disc[++cnt]=a[i][j];
    sort(disc+1,disc+cnt+1);
    cnt=unique(disc+1,disc+cnt+1)-disc-1;
    F(i,1,n) F(j,1,m) a[i][j]=lower_bound(disc+1,disc+cnt+1,a[i][j])-disc;
    F(i,1,n){
        F(j,1,m) ans+=s2[a[i][j]]*i-s1[a[i][j]];
        F(j,1,m) s1[a[i][j]]+=i,s2[a[i][j]]++;
    }
    F(i,1,cnt) s1[i]=s2[i]=0;
    F(j,1,m){
        F(i,1,n) ans+=s2[a[i][j]]*j-s1[a[i][j]];
        F(i,1,n) s1[a[i][j]]+=j,s2[a[i][j]]++;
    }
    printf("%lld\n",ans*2);
    fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
    return 0;
}

F

更签到的题，不讲了

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
    int FF=0,RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    return FF*RR;
}
int n;
map<string,int> mp;
int main(){
    cin>>n;
    F(i,1,n){
        string s;cin>>s;
        mp[s]++;
    }
    for(auto it:mp) if(it.second*2>n){ cout<<it.first<<'\n';exit(0);}
    cout<<"uh-oh"<<'\n';
    fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
    return 0;
}

G

不难的题
不难想到二分，然后的 \(nk\) \(dp\) 就比较显然，需要前缀和优化
时间复杂度 \(O(nk\log n)\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
    int FF=0,RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    return FF*RR;
}
const int N=200100,K=10;
int n,m,k,l[K],s[N],pref[N],f[N][K];
char str[N];
bool a[N];
bool check(int mid){
    memset(f,0x3f,sizeof(f));
    F(i,0,mid-1) f[i][0]=0;
    F(i,mid,n){
        int pos=pref[i-mid];
        if(!pos){ f[i][0]=f[i-1][0],f[i][1]=min(f[i-1][1],i-s[i]);continue;}
        F(j,1,k) f[i][j]=f[pos-1][j-1]+i-pos-(s[i]-s[pos]);
        F(j,0,k) f[i][j]=min(f[i][j],f[i-1][j]);
    }
    return f[n][k]<=m;
}
int main(){
    n=read(),m=read(),k=read();scanf("%s",str+1);
    F(i,1,n) a[i]=str[i]-48,s[i]=s[i-1]+a[i];
    int cur=0;
    F(i,1,n){
        if(!a[i]) cur=i;
        pref[i]=cur;
    }
    if(!check(1)){ puts("-1");exit(0);}
    int l=0,r=n+1;
    while(l<r-1){
        int mid=(l+r)>>1;
        check(mid)?l=mid:r=mid;
    }
    printf("%d\n",l);
    fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
    return 0;
}

I

有点暴力的题，感觉题面吓人导致过的队有点少
一个易想到的判断是一个字母的出现次数，但这会有冲突
于是我打了个表，发现冲突很少，且每个冲突的出现次数都很小
于是可以把冲突的字母暴力匹配然后判断即可
时间复杂度 \(O(\)能过\()\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
    int FF=0,RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    return FF*RR;
}
const int N=60;
int n,rv[N],id[N];
bool vis[N];
int gt(char x){
    if('a'<=x&&x<='z') return x-'a';
    return 26+x-'A';
}
vector<int> inc[N*N*2];
int len,CNT[N],cnt[N];
int ID1[N],ID2[N],dy[N];
map<pii,int> mp2;
map<int,int> mp1;
string s[N*N];
int L[N],R[N];
bool dfs(int dep){
    if(dep>len){
        map<int,int> tmpmp1=mp1;
        map<pii,int> tmpmp2=mp2;
        F(i,1,len) rv[ID1[dy[i]]]=ID2[i];
        bool flg=1;
        F(i,0,n-1){
            F(j,0,n-1){
                int t=i*j;
                int x=t/n,y=t%n;
                if(!x){
                    if(rv[y]!=-1){
                        if(!tmpmp1[rv[y]]){ flg=0;break;}
                        tmpmp1[rv[y]]--;
                    }
                }
                else if(rv[x]!=-1&&rv[y]!=-1){
                    if(!tmpmp2[make_pair(rv[x],rv[y])]){ flg=0;break;}
                    tmpmp2[make_pair(rv[x],rv[y])]--;
                }
            }
            if(!flg) break;
        }
        if(flg) return true;
        return false;
    }
    F(j,L[dep],R[dep]) if(!vis[j]){
        dy[dep]=j,vis[j]=1;
        if(dfs(dep+1)) return true;
        vis[j]=0;
    }
    return false;
}
void work(){
    n=read();
    F(i,0,n-1) CNT[i]=cnt[i]=0;
    mp2.clear(),mp1.clear();
    F(i,0,n*n*2) inc[i].clear();
    F(i,1,n*n){
        cin>>s[i];
        F(j,0,SZ(s[i])) CNT[gt(s[i][j])]++;
        if(s[i].size()==2) mp2[{gt(s[i][0]),gt(s[i][1])}]++;
        else mp1[gt(s[i][0])]++;
    }
    F(i,0,n-1) inc[CNT[i]].pb(i);
    F(i,0,n-1) F(j,0,n-1){
        int t=i*j;
        if(!(t/n)) cnt[t%n]++;
        else cnt[t/n]++,cnt[t%n]++;
    }
    F(i,0,n-1) id[i]=i;
    F(i,0,n-1) rv[i]=-1;
    sort(id,id+n,[&](int x,int y){ return cnt[x]<cnt[y];});
    for(int i=0;i<n;){
        int j=i;
        while(j<n-1&&cnt[id[j+1]]==cnt[id[i]]) j++;
        if(!(j-i)) rv[id[i]]=inc[cnt[id[i]]][0];
        i=j+1;
    }
    len=0;
    for(int i=0;i<n;){
        int j=i;
        while(j<n-1&&cnt[id[j+1]]==cnt[id[i]]) j++;
        if(j-i>0){
            int tlen=len;
            F(k,i,j) ID1[++tlen]=id[k],L[tlen]=len+1,R[tlen]=len+j-i+1;
            for(auto x:inc[cnt[id[i]]]) ID2[++len]=x;
        }
        i=j+1;
    }
    if(len){
        F(k,1,len) vis[k]=0;
        dfs(1);
    }
    F(i,0,n-1){
        if(rv[i]<26) putchar('a'+rv[i]);
        else putchar('A'+rv[i]-26);
    }
    puts("");
}
int main(){
    int T=read();
    while(T--) work();
    fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
    return 0;
}

J

\(sb\) 题，直接魔改最短路，然后枚举最长边即可
时间复杂度 \(O(m\log m)\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
    int FF=0,RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    return FF*RR;
}
const int N=300100,M=1000100,inf=2e9;
int n,m;
int e[M<<1],w[M<<1],ne[M<<1],h[N],idx;
void add(int x,int y,int z){ e[idx]=y,w[idx]=z,ne[idx]=h[x],h[x]=idx++;}
bool vis[N];
priority_queue<pii,vector<pii>,greater<pii> > pq;
void dij(int S,int *d){
    F(i,1,n) d[i]=inf,vis[i]=0;
    d[S]=0,pq.push({0,S});
    while(!pq.empty()){
        int u=pq.top().second;pq.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=h[u];~i;i=ne[i]){
            int v=e[i];
            if(max(d[u],w[i])<d[v]) d[v]=max(d[u],w[i]),pq.push({d[v],v});
        }
    }
}
int d[2][N];
int main(){
    n=read(),m=read();
    ms(h,-1);
    F(i,1,m){
        int x=read(),y=read(),z=read();
        add(x,y,z),add(y,x,z);
    }
    dij(1,d[0]),dij(n,d[1]);
    int ans=inf+100;
    F(i,0,idx-1){
        int x=e[i],y=e[i^1];
        if(d[0][x]<=w[i]&&d[1][y]<=w[i]) chkmin(ans,w[i]+max(d[0][x],d[1][y]));
    }
    for(int i=h[1];~i;i=ne[i]) if(e[i]==n) chkmin(ans,w[i]);
    printf("%d\n",ans);
    fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
    return 0;
}

K

首先可以发现一个性质是一个连通块只可能是一段路径，因为路径两端是最大值和次大值一定是最优的，其他的分开这个连通块更优

然后可以设计出一个朴素的 \(dp\) 做法是：
令 \(f_{i,j}\) 为 \(i\) 的子树中一端权值为 \(j\) 的最大权值和
\(g_i\) 为 \(i\) 的子树能形成的最大权值和

合并子树 \(v\) 时：
\(f_{i,j}=\max\{f_{i,j}+g_v,f_{v,j}+otherg\}\)
\(g_i=\max\{f_{u,j}+f_{v,k}+min(j,k)\}\)

发现上面的东西可以套线段树合并，直接套即可
时间复杂度 \(O(n\log n)\)

这道题感觉 \(dp\) 的设计比较巧妙

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
    int FF=0,RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    return FF*RR;
}
const int N=500100;
const LL inf=1e16;
int n;LL g[N],G;
int cnt,disc[N],w[N];
int e[N<<1],ne[N<<1],h[N],IDX;
int root[N],idx;
struct Node{ LL mx1,mx2,tag;int lc,rc;}seg[N*30];
void down(int x,LL tg){ if(x) seg[x].mx1+=tg,seg[x].mx2+=tg,seg[x].tag+=tg;}
void pushdown(int x){ down(seg[x].lc,seg[x].tag),down(seg[x].rc,seg[x].tag),seg[x].tag=0;}
void calc(int p,int q,int l,int r,LL mx1,LL mx2){
    if(!p&&!q) return;
    if(!p){ chkmax(G,mx1+seg[q].mx2);return;}
    if(!q){ chkmax(G,mx2+seg[p].mx2);return;}
    if(l==r){
        chkmax(mx1,seg[p].mx1),chkmax(mx2,seg[q].mx1);
        chkmax(G,max(seg[p].mx2+mx2,seg[q].mx2+mx1));return;
    }
    pushdown(p),pushdown(q);
    int mid=(l+r)>>1;
    calc(seg[p].lc,seg[q].lc,l,mid,max(mx1,seg[seg[p].rc].mx1),max(mx2,seg[seg[q].rc].mx1));
    calc(seg[p].rc,seg[q].rc,mid+1,r,mx1,mx2);
}
int insert(int l,int r,int pos){
    int p=++idx;seg[p].mx1=0,seg[p].mx2=disc[pos];
    if(l==r) return p;
    int mid=(l+r)>>1;
    if(mid>=pos) seg[p].lc=insert(l,mid,pos);
    else seg[p].rc=insert(mid+1,r,pos);
    return p;
}
int merge(int p,int q,int l,int r,LL coef1,LL coef2){
    if(!p&&!q) return 0;
    if(!p){ seg[q].mx1+=coef2,seg[q].mx2+=coef2,seg[q].tag+=coef2;return q;}
    if(!q){ seg[p].mx1+=coef1,seg[p].mx2+=coef1,seg[p].tag+=coef1;return p;}
    if(l==r){ seg[p].mx1=max(seg[p].mx1+coef1,seg[q].mx1+coef2),seg[p].mx2=max(seg[p].mx2+coef1,seg[q].mx2+coef2);return p;}
    pushdown(p),pushdown(q);
    int mid=(l+r)>>1;
    seg[p].lc=merge(seg[p].lc,seg[q].lc,l,mid,coef1,coef2);
    seg[p].rc=merge(seg[p].rc,seg[q].rc,mid+1,r,coef1,coef2);
    seg[p].mx1=max(seg[seg[p].lc].mx1,seg[seg[p].rc].mx1);
    seg[p].mx2=max(seg[seg[p].lc].mx2,seg[seg[p].rc].mx2);return p;
}
void dfs(int u,int fa){
    LL sumg=0;root[u]=insert(1,n,w[u]);
    for(int i=h[u];~i;i=ne[i]){
        int v=e[i];if(v==fa) continue;
        dfs(v,u);
        g[u]+=g[v],G=0;calc(root[u],root[v],1,n,-inf,-inf);chkmax(g[u],G);
        root[u]=merge(root[u],root[v],1,n,g[v],sumg);
        sumg+=g[v];
    }
}
void add(int x,int y){ e[IDX]=y,ne[IDX]=h[x],h[x]=IDX++;}
int main(){
    seg[0].mx1=-inf,seg[0].mx2=-inf;
    n=read();
    F(i,1,n) w[i]=read(),disc[++cnt]=w[i];
    sort(disc+1,disc+n+1);
    int cnt=unique(disc+1,disc+n+1)-disc-1;
    F(i,1,n) w[i]=lower_bound(disc+1,disc+cnt+1,w[i])-disc;
    ms(h,-1);
    F(i,1,n-1){
        int x=read(),y=read();
        add(x,y),add(y,x);
    }
    dfs(1,-1);
    printf("%lld\n",g[1]);
    fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
    return 0;
}

标签：ch,int,题解,hefei,seg,long,FF,ucup,define
From： https://www.cnblogs.com/Farmer-djx/p/17880274.html

相关文章

  • python HTML文件标题解析问题的挑战
    引言在网络爬虫中，HTML文件标题解析扮演着至关重要的角色。正确地解析HTML文件标题可以帮助爬虫准确地获取所需信息，但是在实际操作中，我们常常会面临一些挑战和问题。本文将探讨在Scrapy中解析HTML文件标题时可能遇到的问题，并提供解决方案。问题背景在解析HTML文件标题的过程中，......
  • Error: error:0308010C:digital envelope routines::unsupported 【问题解决】【转载
    原文链接：  https://www.cnblogs.com/jaxu/p/17171211.html今天早上打开电脑，更新了日常工作的github仓库，然后就是习惯性地执行了"npminstall"，发现报了下面这个错误：Error:error:0308010C:digitalenveloperoutines::unsupported顺便看了一下错误堆栈，发现是一个Node......
  • 线性代数题解
    前言写完了这道题我好想刚明白一点最小割？？？UU好闪，拜谢UU。题解首先，我们可以发现若第\(i\)行的\(B\)没选，那么第\(i\)列的\(B\)也不选，所以此时对于行和列是等价的。若\(A_i\)是\(0\)，则会减少贡献\(\sum_{j}B_{i,j}\)。否则会减少贡献\(C_i\)。当\(A_i\)是\(0\)......
  • CF603题解
    CF603CodeforcesRound334(Div.1)CF603AlinkCF603A题意现有一个长度为\(n\)的01串,可以进行一次区间翻转(起点终点随意,并且区间里的值1变0,0变1),得到一个新的01串,使得得到的新的01串中的一个子串最长(子串不一定连续),且这个子串是01间隔的，没......
  • CF1824B1 LuoTianyi and the Floating Islands (Easy Version) 题解
    题意：思路：由于$k∈[1，3]$，分类讨论：当$k=1$时，有人结点自身即为好结点，每种情况的期望为$\frac{1}{n}$，$n$种情况的期望和为$1$。最终答案即为$1$。当$k=2$时，$2$个有人结点之间的路径上的结点即为好结点，那么问题转化为：树上所有路径的结点......
  • ABC325G offence 题解
    给出一个长为\(n\)的字符串和非负整数\(k\)。你可以进行以下操作若干次，使得最终字符串长度最小。选择一个字串of。然后删掉of以及这之后的\(i\)个字符。\(i\)由你决定，但要满足\(0\leqi\leqk\)。输出这个最小长度。\(1\leqn,k\leq300\)。做完以后感觉很简单。但......
  • CTFpwn格式化字符串两种应用及2023ISCTF的fmt题解wp
    三个例子的引入目前我遇到的格式化字符串漏洞(formatstring,后文简称fmt)主要存在于printf函数，本文也就以printf举例。例一，标准格式的printf read(0,buf,33);printf("%s",buf);例二，占位符与变量 printf("%d%c%s",a,b,c);//%d%c%s会访问变量以输出整型，字符等。其中a，b，c为三......
  • [AGC032D] Rotation Sort 题解
    题目链接点击打开链接题目解法题目中的操作可以理解为一个点移动位置首先给出一个结论：每个点只会动至多一次考虑\(dp\)一个比较妙的状态设定是\(f_i\)表示\(i\)不动的方案数不妨枚举\(j\)表示上一个不动点，限制是\(j<i\)且\(p_j<p_i\)中间满足\(j<k<i\)且\(p_......
  • [AGC037D] Sorting a Grid 题解
    题目链接点击打开链接题目解法从后往前推一下，可以得到\(C\)一定要把每一行的数都归位到那一行，\(B\)一定要每一列的目标行数互不相同考虑构造\(B\)这个限制看起来略有些网络流，所以考虑如何建图令\(a_{i,j}\)的目标行数为\(ln_{i,j}\)，我们由\(i\toln_{i,j}\)连边不......
  • [ABC254E] Small d and k 题解
    题目传送门一道暴力题。度数和\(k\)那么小？直接暴力\(n\)遍bfs，注意bfs的队列只能push距离不超过\(3\)的点。但有个问题，每次bfs都需要清空一次距离数组，这样子的时间复杂度是\(O(n^2)\)的。但也不难想到，距离数组中被赋值的地方不会很多，记录一下就行。Code#include......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99