今天无聊的我又来切树形dp了，貌似我与树形dp有仇似的。
n个节点的树
第i个节点权值为 n<=10^6
−100<=ai<=100
问是否能够删除掉两条边,使得该树分成三个不为空,并且每部分权值之和相等.
无解输出−1 否则输出要删除边(u−>v)的v节点序号.
说白了就是把一棵树分成三块连通图，并且每个连通图权值相同，那么我们不管怎么切都会切出以某个结点为根的子树。由于每个点的权值都是整数，那么我们先用总权值 mod 3看看能不能整除，如果不能就输出-1，如果可以那么每个子树肯定权值都是 w/3 （w为总权值）。接着就跑树形dp咯，设f[x]代表以x为根的子树的权值和（包括x在内），如果某一个f[x]== w/3 我们就统计一下，如果一个树上有三个这样的根节点，那么就把这三个根节点和他们的父亲的边切了，这样就得到了我们想要的结果了，所以统计一下这样的点的数量就行，最后判断一下是否三个这样的点。
接下来就是愉快的代码时间：
#include<iostream>
#include<cstdio>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#define maxn 1000005
using namespace std; struct edge
{
int next;
int to;
}g[maxn<<]; inline int read()
{
char c=getchar();
int res=,x=;
while(c<''||c>'')
{
if(c=='-')
x=-;
c=getchar();
}
while(c>=''&&c<='')
{
res=res*+(c-'');
c=getchar();
}
return x*res;
} int n,num,aa,bb,root,sum,cnt,ans[];
int last[maxn],f[maxn],d[maxn]; inline void add(int from,int to)
{
g[++num].next=last[from];
g[num].to=to;
last[from]=num;
} void dfs(int x)
{
d[x]=;
for(int i=last[x];i;i=g[i].next)
{
int v=g[i].to;
if(!d[v])
{
dfs(v);
f[x]+=f[v];
}
}
if(f[x]==sum)
{
ans[++cnt]=x;
f[x]=;
}
} int main()
{
n=read();
for(int i=;i<=n;i++)
{
aa=read();bb=read();
f[i]=bb;
sum+=bb;
if(aa==)
{
root=i;
}
else
{
add(i,aa);
add(aa,i);
}
}
if(sum%!=)
{
printf("-1\n");
return ;
}
else
{
sum=sum/;
dfs(root);
if(cnt<=)
printf("-1");
else
printf("%d %d",ans[],ans[]);
return ;
}
}
If you fail, don't forget to learn your lesson.
如果你失败了，千万别忘了汲取教训。
--snowy
2019-01-16 12:02:52