本文主要是介绍J.绝妙的平衡，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
解题思路
- 对于一个以染成红色的点为根的子树，要使其权值之和为3的倍数
- 则与其子树中的红色点无关，至于白色点数有关
- 若除去子树中的红色点后，剩余包括其自身共有k个
- 若
，则无解，即只有一个红色叶子点
- 若
，则除自身为2外，子树中还要有一个白点为2，其余为1
- 若
，则除自身为2外，子树中白点全为1
- 若
，则全为1
- 不用建树，用并查集维护集合，集合要么是全为白色，要么至多有一个红色
- 对于白点向红色点的连边，并查集不用合并
import java.io.*;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.BitSet;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.Vector;public class Main{static long md=(long)998244353;static long Linf=Long.MAX_VALUE/2;static int inf=Integer.MAX_VALUE/2;static int[] fa;static int[] size;static int find(int x) {if(x==fa[x])return x;else return fa[x]=find(fa[x]);}public static void main(String[] args) throws IOException{AReader input=new AReader();PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));int n=input.nextInt();String string=" "+input.next();char[] s=string.toCharArray();fa=new int[n+1];size=new int[n+1];for(int i=1;i<=n;++i) {fa[i]=i;size[i]=1;}for(int i=2;i<=n;++i) {int x=input.nextInt();if(s[i]=='R')continue;int fx=find(x);int fy=find(i);if(fx!=fy) {fa[fy]=fx;size[fx]+=size[fy];}}int[] needtwo=new int[n+1];int[] ans=new int[n+1];boolean ok=true;for(int i=1;i<=n;++i) {if(fa[i]!=i) {int x=fa[i];if(needtwo[x]!=0) {needtwo[x]--;ans[i]=2;}else {ans[i]=1;}continue;}int sheng=size[i]%3;if(sheng==0) {ans[i]=1;}else if(sheng==1){if(size[i]==1&&s[i]=='R') {ok=false;break;}needtwo[i]=1;ans[i]=2;}else if(sheng==2){ans[i]=2;}}if(!ok)out.print("-1");else {for(int i=1;i<=n;++i) {out.print(ans[i]);}}out.flush();out.close();}//System.out.println();//out.println();staticclass AReader{ BufferedReader bf;StringTokenizer st;BufferedWriter bw;public AReader(){bf=new BufferedReader(new InputStreamReader(System.in));st=new StringTokenizer("");bw=new BufferedWriter(new OutputStreamWriter(System.out));}public String nextLine() throws IOException{return bf.readLine();}public String next() throws IOException{while(!st.hasMoreTokens()){st=new StringTokenizer(bf.readLine());}return st.nextToken();}public char nextChar() throws IOException{//确定下一个token只有一个字符的时候再用return next().charAt(0);}public int nextInt() throws IOException{return Integer.parseInt(next());}public long nextLong() throws IOException{return Long.parseLong(next());}public double nextDouble() throws IOException{return Double.parseDouble(next());}public float nextFloat() throws IOException{return Float.parseFloat(next());}public byte nextByte() throws IOException{return Byte.parseByte(next());}public short nextShort() throws IOException{return Short.parseShort(next());}public BigInteger nextBigInteger() throws IOException{return new BigInteger(next());}public void println() throws IOException {bw.newLine();}public void println(int[] arr) throws IOException{for (int value : arr) {bw.write(value + " ");}println();}public void println(int l, int r, int[] arr) throws IOException{for (int i = l; i <= r; i ++) {bw.write(arr[i] + " ");}println();}public void println(int a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}public void print(int a) throws IOException{bw.write(String.valueOf(a));}public void println(String a) throws IOException{bw.write(a);bw.newLine();}public void print(String a) throws IOException{bw.write(a);}public void println(long a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}public void print(long a) throws IOException{bw.write(String.valueOf(a));}public void println(double a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}public void print(double a) throws IOException{bw.write(String.valueOf(a));}public void print(char a) throws IOException{bw.write(String.valueOf(a));}public void println(char a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}}
}
这篇关于J.绝妙的平衡的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
