Codeforces Round#530(Div.2)ABCDまとめ

もともと4つの問題rank 800+が安定して点数をつけて、それから唯一の1 AのC問題が最終測定を掛けて、瞬間rank 2000+、49点を落としました.の(わぁ)
A:雪玉の最初の重さと高さをあげます.毎秒1メートル下がります.1メートル下がるごとに重さが増えます.次にx 1,h 1,x 2を2つあげます.h 2は高さh 1が雪球の重量をx 1減少させ、高さh 2が雪球の重量をx 2減少させます(もちろん対応する高さを増加させます).雪球の最小重量は0で、h=0になったときの雪球の重量を求めます.
この問題はつまらないと思います...問題に署名するのはまだこんなに面倒で、h 1とh 2を記録して、もう一つのforが終わります.
B:タイトルの図のように並べて、最低何本の木の棒がn個の正方形に並べられるかを聞いてください.
明らかに横一縦に上と左に沿って並べられています.の自分で公式を押して、この问题の解法はとても多いです...
C:本当にtmの穴、あなたに小文字と*を含みますか?の文字列、保証*?前に文字があります.*前の文字を削除したり、前の文字を保持したり、前の文字を任意にコピーしたりすることができます.前の文字を削除するか、前の文字を保持するしかありません.あなたにすべての*を聞きますか?使用方法を選択した後、文字列の長さをnにできるかどうかを選択します.
穴の点はすでに赤色の寸法をつけて、もし1回だけコピーするならば!掛けて!終わりだ!測れ!(話しすぎて涙だらけ)
統計してみると*と?の数を入力して、タイトル通りに入力または削除すればいいです.細部に注意する.
D:n-1個の数a[i](2<=i<=n)を与え、iの祖先がa[i](縁がなく、木を構成することを保証し、1がルートノードであることを示し、n個の数s[i]を与える.
各ノードには権限値がありますが、不明です.
iが奇数層ノードである場合、s[i]はルートノード(1番ノード)からi番ノードまでのすべての点の重み値の和(i番目の点を含む)であり、そうでない場合s[i]は-1である.
すべてのノードの重み値の和を最小限に抑えるために、各ポイントに重み値を割り当ててください.正当なシナリオが存在しない場合は、-1を出力します.
考え方:
実は木が私たちに与えた後、1つのdfsだけで奇数層と偶数層のノードを簡単に確定することができます.
総重み値を最小限に抑えるには、ブランチノードにできるだけ大きな値を負わせるに違いありません.
dp配列を用いて
dp[i]=s[i]iは奇数層ノード
min(dp[i],dp[v])iは偶数層ノード,vはiノードの直接サブノードである
次にdfsで、valはルートノードから現在のノードへの重み値と、奇数層の点についてs[i]
偶数層のノードの場合、dp[i]
コード:

#include
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3fLL
using namespace std;
const int maxn=200010;
int n,m,k,x,y;
ll a[maxn],s[maxn];
ll c[maxn],dp[maxn];
ll ans,ct,cnt,tmp,flag;
vectorvc[maxn];
void dfs(int u,int fa,int dep)
{
    c[u]=dep;
    if(dep&1) dp[u]=s[u];
    //if(dep&1) dp[u]=max(dp[u],s[u]);
    for(int i=0;is[u]) {flag=0;return;}
        else a[u]=s[u]-val;
    }
    else
    {
        if(dp[u]