题目链接：

---

 

问能否将一棵带点权的书分成点权$3$块，求任意方案。

 

其实考虑一棵以$x$为根的子树权值为${\frac{1}{3}\sum val[i]}$之后它就一定要作为单独的一块了，那么DFS一遍即可。

---

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 using namespace std; 9 #define maxn 100001010 #define llg long long 11 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);12 llg n,m,ans[maxn],tot,val[maxn],size[maxn],sum,dad[maxn],root;13 vector
            
             a[maxn];14 15 void dfs(llg x,llg fa)16 {17 if (tot==2) return ;18 llg w=a[x].size(),v;19 size[x]=val[x];20 for (llg i=0;i
             
              >n;37 for (llg i=1;i<=n;i++)38 {39 scanf("%I64d%I64d",&dad[i],&val[i]);40 if (dad[i]==0) root=i;41 a[dad[i]].push_back(i);42 sum+=val[i];43 }44 }45 46 int main()47 {48 // yyj("C");49 init();50 if (sum%3!=0) {cout<<-1; return 0;}51 sum/=3;52 dfs(root,0);53 sort(ans+1,ans+tot+1);54 for (llg i=1;i<=n;i++)55 if (ans[i]==root)56 {57 cout<<-1;58 return 0;59 }60 if (tot>=2) { for (llg i=1;i<=tot;i++) cout<
              
               <<" "; }else cout<<-1;61 return 0;62 }