AtCoder Grant Contest 010 C-Cleaning dfs+論理+dp思想
8948 ワード
标题:1本の木が与えられ、各ノードの重み値はAiであり、毎回2つのリーフノードを選択し、2つのリーフノード間のパス上の重み値-1を選択することができる.最後に木全体の重みを0にすることができるかどうかを尋ねます.
解法:解の存在性を検証し、実行可能な解のセットを見つけてみましょう.この問題は末端の状況から考えるとdpを容易に考え出すことができる.
葉以外のノードを勝手に探して、木全体の根として、今この根のある木を分析します.
まず経路を分類することができ、1つの非葉ノードAに対して、その経路を通過することは2つの状況に分けることができる.
1.サブノードを通過する.
2.サブノードを2つ通過します.
パスが2つのサブノードを通過することは、この道が上に行かなくても、Aの父に影響を与えないことを意味します.
パスがサブノードを通過することは、別の端点がAをルートとするサブツリーにないため、さらに上へ伝達する必要があることを意味する.
次にdfsの詳細を考えます.
1.リーフノードを考慮すると、リーフノードはパスの端点であるため、リーフノードの重み値は必ず上に伝達されなければならない.
2.非葉ノードA’を考慮すると、既知の重み値はAiであり、その子ノードから伝達される重み値とtotを設定し、そのうち第1のエッジはx 1に寄与し、第2のエッジはx 2に寄与し、そのうちx 1は上へ伝達される必要がある.方程式を簡単にリストします.
x 1+x 2=Ai,2*x 2+x 1=totは,x 1とx 2の値を解くことができる.
次に、x 1とx 2の合法性を判断します.
1.x 1とx 2はいずれも0以上である.
2.x 1とx 2がともに0以上である場合、このような状況を本当に描くことができる.観察によると、息子が上に伝達した重みの分配が奇形のときだけ描けないことが分かった.tmを息子における重み値の最大値とし,tm>Aiの場合,x 1本目の経路,x 2本目の2つ目の経路を描くことができない.シミュレーションをすると見えます.
最後に、木全体のルートノードがx 1が0に等しいかどうかを見て、もしそうなら、ルートノードを通るのは2番目のエッジしかないので、実行可能な解が見つかったことを証明します.
解法:解の存在性を検証し、実行可能な解のセットを見つけてみましょう.この問題は末端の状況から考えるとdpを容易に考え出すことができる.
葉以外のノードを勝手に探して、木全体の根として、今この根のある木を分析します.
まず経路を分類することができ、1つの非葉ノードAに対して、その経路を通過することは2つの状況に分けることができる.
1.サブノードを通過する.
2.サブノードを2つ通過します.
パスが2つのサブノードを通過することは、この道が上に行かなくても、Aの父に影響を与えないことを意味します.
パスがサブノードを通過することは、別の端点がAをルートとするサブツリーにないため、さらに上へ伝達する必要があることを意味する.
次にdfsの詳細を考えます.
1.リーフノードを考慮すると、リーフノードはパスの端点であるため、リーフノードの重み値は必ず上に伝達されなければならない.
2.非葉ノードA’を考慮すると、既知の重み値はAiであり、その子ノードから伝達される重み値とtotを設定し、そのうち第1のエッジはx 1に寄与し、第2のエッジはx 2に寄与し、そのうちx 1は上へ伝達される必要がある.方程式を簡単にリストします.
x 1+x 2=Ai,2*x 2+x 1=totは,x 1とx 2の値を解くことができる.
次に、x 1とx 2の合法性を判断します.
1.x 1とx 2はいずれも0以上である.
2.x 1とx 2がともに0以上である場合、このような状況を本当に描くことができる.観察によると、息子が上に伝達した重みの分配が奇形のときだけ描けないことが分かった.tmを息子における重み値の最大値とし,tm>Aiの場合,x 1本目の経路,x 2本目の2つ目の経路を描くことができない.シミュレーションをすると見えます.
最後に、木全体のルートノードがx 1が0に等しいかどうかを見て、もしそうなら、ルートノードを通るのは2番目のエッジしかないので、実行可能な解が見つかったことを証明します.
#include
#include
#include
#include
using namespace std;
typedef long long ll;
typedef unsigned int uii;
const int maxn=100005;
int n,a,b;
ll A[maxn];
vector tr[maxn];
ll dfs(int u,int fa) {
if (tr[u].size()==1)
return A[u];
ll tot=0,x2=0,x1=0,mm,tm=0;
for (uii i=0;i0&&fa==-1)) {
puts("NO");
exit(0);
}
return x1;
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;++i)
scanf("%lld",&A[i]);
if (n==1) {
puts(A[1]?"NO":"YES");
return 0;
}
for (int i=0;i1) {
dfs(i,-1);
break;
}
puts("YES");
}
return 0;
}