daily 2

CF 1060E

int main(){
    int n;
    cin>>n;
    vector<vector<int>>E(n+1);
    for(int i=1;i<=n-1;++i){
        int u,v;
        cin>>u>>v;
        E[u].push_back(v);
        E[v].push_back(u);
    }
    vector<ll>sz(n+1),dep(n+1);
    function<void(int,int)>dfs=[&](int x,int f){
        sz[x]=1;
        for(int v:E[x]){
            if(v==f)continue;
            dep[v]=dep[x]+1;
            dfs(v,x);
            sz[x]+=sz[v];
        }
    };
    dfs(1,0);
    ll ans=0;
    ll num=0;
    for(int i=1;i<=n;++i){
        ans+=sz[i]*(n-sz[i]);
        if(dep[i]%2==1)++num;
    }
    ans+=(num)*(n-num);
    cout<<ans/2<<'\n';
}

CF 1114D

int dp[N][N];
int a[N];
int num;
int main(){
    int n;
    cin>>n;
    int pre=-1;

    for(int i=1;i<=n;++i){
        int x;
        cin>>x;
        if(x!=pre){
            a[++num]=x;
        }
        pre=x;
    }
    for(int len=1;len<=num;++len){
        for(int l=1;l+len<=num;++l){
            int r=l+len;
            if(a[l]==a[r]){
                dp[l][r]=dp[l+1][r-1]+1;
            }else{
                dp[l][r]=min(dp[l][r-1],dp[l+1][r])+1;
            }
        }
    }
    cout<<dp[1][num]<<'\n';
}