using System; using System.Buffers; using System.Collections.Generic; using System.Diagnostics; using System.IO; using System.Linq; using System.Numerics; using System.Runtime.CompilerServices; using System.Runtime.InteropServices; using System.Runtime.Intrinsics.X86; using System.Text; using YukicoderContest308.Problems; namespace YukicoderContest308.Problems { public class ProblemF : ProblemBase { public ProblemF() : base(false) { } [MethodImpl(MethodImplOptions.AggressiveOptimization)] protected override void SolveEach(IOManager io) { var n = io.ReadInt(); var queryCount = io.ReadInt(); var costs = io.ReadIntArray(n); var inIndex = new int[n]; var outIndex = new int[n]; var index = 0; var tree = Enumerable.Repeat(0, n).Select(_ => new List()).ToArray(); for (int i = 0; i < n - 1; i++) { var u = io.ReadInt(); var v = io.ReadInt(); u--; v--; tree[u].Add(v); tree[v].Add(u); } EularTour(0, -1, ref index); var segTree = new SegmentTree(2 * n); for (int i = 0; i < inIndex.Length; i++) { segTree[inIndex[i]] = new Xor(costs[i]); } for (int q = 0; q < queryCount; q++) { var type = io.ReadInt(); var x = io.ReadInt(); var y = io.ReadInt(); x--; if (type == 1) { segTree[inIndex[x]] = new Xor(segTree[inIndex[x]].Value ^ y); } else { io.WriteLine(segTree.Query(inIndex[x], outIndex[x]).Value); } } void EularTour(int current, int parent, ref int index) { inIndex[current] = index++; foreach (var child in tree[current]) { if (child == parent) { continue; } EularTour(child, current, ref index); } outIndex[current] = index++; } } readonly struct Xor : IMonoid { readonly public int Value; public Xor Identity => new Xor(0); public Xor(int value) { Value = value; } public Xor Merge(Xor other) { return new Xor(Value ^ other.Value); } } public interface ISemigroup { public TSet Merge(TSet other); } public interface IMonoid : ISemigroup { public TSet Identity { get; } } public interface IMonoidWithAct : IMonoid where TMonoid : IMonoid where TOperator : IMonoid { public TMonoid Act(TMonoid monoid); } public class SegmentTree where T : struct, IMonoid { // 1-indexed protected readonly T[] _data; public int Length { get; } protected Span Leaves => _data.AsSpan(HalfLength, Length); protected int HalfLength => _data.Length >> 1; /// /// 単位元で初期化します。 /// public SegmentTree(int n) : this(n, default(T).Identity) { } /// /// 指定した値で初期化します。 /// public SegmentTree(int n, T initialValue) { if (n < 0) { throw new ArgumentOutOfRangeException(); } Length = n; _data = new T[1 << (CeilPow2(n) + 1)]; _data.AsSpan(HalfLength, Length).Fill(initialValue); Build(); } /// /// 指定したデータ列で初期化します。 /// public SegmentTree(ReadOnlySpan values) { Length = values.Length; _data = new T[1 << (CeilPow2(values.Length) + 1)]; values.CopyTo(Leaves); Build(); } public virtual T this[int index] { get => Leaves[index]; set { Leaves[index] = value; index += HalfLength; while ((index >>= 1) > 0) { _data[index] = _data[(index << 1) + 0].Merge(_data[(index << 1) + 1]); } } } public T Query(Range range) => Query(range.Start, range.End); public T Query(Index left, Index right) => Query(left.GetOffset(Length), right.GetOffset(Length)); public virtual T Query(int left, int right) { if (unchecked((uint)left > (uint)Length || (uint)right > (uint)Length || left > right)) { throw new ArgumentOutOfRangeException(); } var sumL = default(T).Identity; var sumR = default(T).Identity; left += HalfLength; right += HalfLength; while (left < right) { if ((left & 1) > 0) { sumL = sumL.Merge(_data[left++]); } if ((right & 1) > 0) { sumR = _data[--right].Merge(sumR); } left >>= 1; right >>= 1; } return sumL.Merge(sumR); } public T QueryAll() => _data[1]; private void Build() { var parents = HalfLength; _data.AsSpan(parents + Length).Fill(default(T).Identity); for (int i = parents - 1; i >= 0; i--) { _data[i] = _data[(i << 1) + 0].Merge(_data[(i << 1) + 1]); } } /// /// [l, r)が条件を満たす最大のrを求めます。 /// public int FindMaxRight(Index left, Predicate predicate) => FindMaxRight(left.GetOffset(Length), predicate); /// /// [l, r)が条件を満たす最大のrを求めます。 /// public virtual int FindMaxRight(int left, Predicate predicate) { // 単位元は条件式を満たす必要がある Debug.Assert(predicate(default(T).Identity)); if (unchecked((uint)left > Length)) { throw new ArgumentOutOfRangeException(); } else if (left == Length) { return Length; } var right = left + HalfLength; var sum = default(T).Identity; do { right >>= BitOperations.TrailingZeroCount(right); var merged = sum.Merge(_data[right]); if (!predicate(merged)) { return DownSearch(right, sum, predicate); } sum = merged; right++; } while ((right & -right) != right); return Length; int DownSearch(int right, T sum, Predicate predicate) { while (right < HalfLength) { right <<= 1; var merged = sum.Merge(_data[right]); if (predicate(merged)) { sum = merged; right++; } } return right - HalfLength; } } /// /// [l, r)が条件を満たす最小のlを求めます。 /// public int FindMinLeft(Index right, Predicate predicate) => FindMinLeft(right.GetOffset(Length), predicate); /// /// [l, r)が条件を満たす最小のlを求めます。 /// public virtual int FindMinLeft(int right, Predicate predicate) { // 単位元は条件式を満たす必要がある Debug.Assert(predicate(default(T).Identity)); if (unchecked((uint)right > Length)) { throw new ArgumentOutOfRangeException(); } else if (right == 0) { return 0; } var left = right + HalfLength; var sum = default(T).Identity; do { left--; left >>= BitOperations.TrailingZeroCount((1 << BitOperations.Log2((uint)left)) | ~left); var merged = _data[left].Merge(sum); if (!predicate(merged)) { return DownSearch(left, sum, predicate); } sum = merged; } while ((left & -left) != left); return 0; int DownSearch(int left, T sum, Predicate predicate) { while (left < HalfLength) { left = (left << 1) + 1; var merged = _data[left].Merge(sum); if (predicate(merged)) { sum = merged; left--; } } return left + 1 - HalfLength; } } protected static int CeilPow2(int n) { var m = (uint)n; if (m <= 1) { return 0; } else { return BitOperations.Log2(m - 1) + 1; } } } } } namespace YukicoderContest308 { class Program { static void Main(string[] args) { IProblem question = new ProblemF(); using var io = new IOManager(Console.OpenStandardInput(), Console.OpenStandardOutput()); question.Solve(io); } } } #region Base Class namespace YukicoderContest308.Problems { public interface IProblem { string Solve(string input); void Solve(IOManager io); } public abstract class ProblemBase : IProblem { protected bool HasMultiTestCases { get; } protected ProblemBase(bool hasMultiTestCases) => HasMultiTestCases = hasMultiTestCases; public string Solve(string input) { var inputStream = new MemoryStream(Encoding.UTF8.GetBytes(input)); var outputStream = new MemoryStream(); using var manager = new IOManager(inputStream, outputStream); Solve(manager); manager.Flush(); outputStream.Seek(0, SeekOrigin.Begin); var reader = new StreamReader(outputStream); return reader.ReadToEnd(); } public void Solve(IOManager io) { var tests = HasMultiTestCases ? io.ReadInt() : 1; for (var t = 0; t < tests; t++) { SolveEach(io); } } protected abstract void SolveEach(IOManager io); } } #endregion #region Utils namespace YukicoderContest308 { public class IOManager : IDisposable { private readonly BinaryReader _reader; private readonly StreamWriter _writer; private bool _disposedValue; private byte[] _buffer = new byte[1024]; private int _length; private int _cursor; private bool _eof; const char ValidFirstChar = '!'; const char ValidLastChar = '~'; public IOManager(Stream input, Stream output) { _reader = new BinaryReader(input); _writer = new StreamWriter(output) { AutoFlush = false }; } [MethodImpl(MethodImplOptions.AggressiveInlining)] private char ReadAscii() { if (_cursor == _length) { _cursor = 0; _length = _reader.Read(_buffer); if (_length == 0) { if (!_eof) { _eof = true; return char.MinValue; } else { ThrowEndOfStreamException(); } } } return (char)_buffer[_cursor++]; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public char ReadChar() { char c; while (!IsValidChar(c = ReadAscii())) { } return c; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public string ReadString() { var builder = new StringBuilder(); char c; while (!IsValidChar(c = ReadAscii())) { } do { builder.Append(c); } while (IsValidChar(c = ReadAscii())); return builder.ToString(); } public int ReadInt() => (int)ReadLong(); [MethodImpl(MethodImplOptions.AggressiveInlining)] public long ReadLong() { long result = 0; bool isPositive = true; char c; while (!IsNumericChar(c = ReadAscii())) { } if (c == '-') { isPositive = false; c = ReadAscii(); } do { result *= 10; result += c - '0'; } while (IsNumericChar(c = ReadAscii())); return isPositive ? result : -result; } [MethodImpl(MethodImplOptions.AggressiveInlining)] private Span ReadChunk(Span span) { var i = 0; char c; while (!IsValidChar(c = ReadAscii())) { } do { span[i++] = c; } while (IsValidChar(c = ReadAscii())); return span.Slice(0, i); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public double ReadDouble() => double.Parse(ReadChunk(stackalloc char[32])); [MethodImpl(MethodImplOptions.AggressiveInlining)] public decimal ReadDecimal() => decimal.Parse(ReadChunk(stackalloc char[32])); public int[] ReadIntArray(int n) { var a = new int[n]; for (int i = 0; i < a.Length; i++) { a[i] = ReadInt(); } return a; } public long[] ReadLongArray(int n) { var a = new long[n]; for (int i = 0; i < a.Length; i++) { a[i] = ReadLong(); } return a; } public double[] ReadDoubleArray(int n) { var a = new double[n]; for (int i = 0; i < a.Length; i++) { a[i] = ReadDouble(); } return a; } public decimal[] ReadDecimalArray(int n) { var a = new decimal[n]; for (int i = 0; i < a.Length; i++) { a[i] = ReadDecimal(); } return a; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public void Write(T value) => _writer.Write(value.ToString()); [MethodImpl(MethodImplOptions.AggressiveInlining)] public void WriteLine(T value) => _writer.WriteLine(value.ToString()); public void WriteLine(IEnumerable values, char separator) { var e = values.GetEnumerator(); if (e.MoveNext()) { _writer.Write(e.Current.ToString()); while (e.MoveNext()) { _writer.Write(separator); _writer.Write(e.Current.ToString()); } } _writer.WriteLine(); } public void WriteLine(T[] values, char separator) => WriteLine((ReadOnlySpan)values, separator); public void WriteLine(Span values, char separator) => WriteLine((ReadOnlySpan)values, separator); public void WriteLine(ReadOnlySpan values, char separator) { for (int i = 0; i < values.Length - 1; i++) { _writer.Write(values[i]); _writer.Write(separator); } if (values.Length > 0) { _writer.Write(values[^1]); } _writer.WriteLine(); } public void Flush() => _writer.Flush(); [MethodImpl(MethodImplOptions.AggressiveInlining)] private static bool IsValidChar(char c) => ValidFirstChar <= c && c <= ValidLastChar; [MethodImpl(MethodImplOptions.AggressiveInlining)] private static bool IsNumericChar(char c) => ('0' <= c && c <= '9') || c == '-'; private void ThrowEndOfStreamException() => throw new EndOfStreamException(); protected virtual void Dispose(bool disposing) { if (!_disposedValue) { if (disposing) { _reader.Dispose(); _writer.Flush(); _writer.Dispose(); } _disposedValue = true; } } public void Dispose() { Dispose(disposing: true); GC.SuppressFinalize(this); } } public static class UtilExtensions { public static bool ChangeMax(ref this T value, T other) where T : struct, IComparable { if (value.CompareTo(other) < 0) { value = other; return true; } return false; } public static bool ChangeMin(ref this T value, T other) where T : struct, IComparable { if (value.CompareTo(other) > 0) { value = other; return true; } return false; } public static void SwapIfLargerThan(ref this T a, ref T b) where T : struct, IComparable { if (a.CompareTo(b) > 0) { (a, b) = (b, a); } } public static void SwapIfSmallerThan(ref this T a, ref T b) where T : struct, IComparable { if (a.CompareTo(b) < 0) { (a, b) = (b, a); } } public static void Sort(this T[] array) where T : IComparable => Array.Sort(array); public static void Sort(this T[] array, Comparison comparison) => Array.Sort(array, comparison); } public static class CollectionExtensions { private class ArrayWrapper { #pragma warning disable CS0649 public T[] Array; #pragma warning restore CS0649 } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static Span AsSpan(this List list) { return Unsafe.As>(list).Array.AsSpan(0, list.Count); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static Span GetRowSpan(this T[,] array, int i) { var width = array.GetLength(1); return MemoryMarshal.CreateSpan(ref array[i, 0], width); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static Span GetRowSpan(this T[,,] array, int i, int j) { var width = array.GetLength(2); return MemoryMarshal.CreateSpan(ref array[i, j, 0], width); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static Span GetRowSpan(this T[,,,] array, int i, int j, int k) { var width = array.GetLength(3); return MemoryMarshal.CreateSpan(ref array[i, j, k, 0], width); } public static void Fill(this T[] array, T value) => array.AsSpan().Fill(value); public static void Fill(this T[,] array, T value) => MemoryMarshal.CreateSpan(ref array[0, 0], array.Length).Fill(value); public static void Fill(this T[,,] array, T value) => MemoryMarshal.CreateSpan(ref array[0, 0, 0], array.Length).Fill(value); public static void Fill(this T[,,,] array, T value) => MemoryMarshal.CreateSpan(ref array[0, 0, 0, 0], array.Length).Fill(value); } public static class SearchExtensions { struct LowerBoundComparer : IComparer where T : IComparable { public int Compare(T x, T y) => 0 <= x.CompareTo(y) ? 1 : -1; } struct UpperBoundComparer : IComparer where T : IComparable { public int Compare(T x, T y) => 0 < x.CompareTo(y) ? 1 : -1; } // https://trsing.hatenablog.com/entry/2019/08/27/211038 public static int GetGreaterEqualIndex(this ReadOnlySpan span, T inclusiveMin) where T : IComparable => ~span.BinarySearch(inclusiveMin, new UpperBoundComparer()); public static int GetGreaterThanIndex(this ReadOnlySpan span, T exclusiveMin) where T : IComparable => ~span.BinarySearch(exclusiveMin, new LowerBoundComparer()); public static int GetLessEqualIndex(this ReadOnlySpan span, T inclusiveMax) where T : IComparable => ~span.BinarySearch(inclusiveMax, new LowerBoundComparer()) - 1; public static int GetLessThanIndex(this ReadOnlySpan span, T exclusiveMax) where T : IComparable => ~span.BinarySearch(exclusiveMax, new UpperBoundComparer()) - 1; public static int GetGreaterEqualIndex(this Span span, T inclusiveMin) where T : IComparable => ((ReadOnlySpan)span).GetGreaterEqualIndex(inclusiveMin); public static int GetGreaterThanIndex(this Span span, T exclusiveMin) where T : IComparable => ((ReadOnlySpan)span).GetGreaterThanIndex(exclusiveMin); public static int GetLessEqualIndex(this Span span, T inclusiveMax) where T : IComparable => ((ReadOnlySpan)span).GetLessEqualIndex(inclusiveMax); public static int GetLessThanIndex(this Span span, T exclusiveMax) where T : IComparable => ((ReadOnlySpan)span).GetLessThanIndex(exclusiveMax); public static int BoundaryBinarySearch(Predicate predicate, int ok, int ng) { while (Math.Abs(ok - ng) > 1) { var mid = (ok + ng) / 2; if (predicate(mid)) { ok = mid; } else { ng = mid; } } return ok; } public static long BoundaryBinarySearch(Predicate predicate, long ok, long ng) { while (Math.Abs(ok - ng) > 1) { var mid = (ok + ng) / 2; if (predicate(mid)) { ok = mid; } else { ng = mid; } } return ok; } public static BigInteger BoundaryBinarySearch(Predicate predicate, BigInteger ok, BigInteger ng) { while (BigInteger.Abs(ok - ng) > 1) { var mid = (ok + ng) / 2; if (predicate(mid)) { ok = mid; } else { ng = mid; } } return ok; } public static double BoundaryBinarySearch(Predicate predicate, double ok, double ng, double eps = 1e-9, int loopLimit = 1000) { var count = 0; while (Math.Abs(ok - ng) > eps && count++ < loopLimit) { var mid = (ok + ng) * 0.5; if (predicate(mid)) { ok = mid; } else { ng = mid; } } return (ok + ng) * 0.5; } public static double Bisection(Func f, double a, double b, double eps = 1e-9, int loopLimit = 100) { double mid = (a + b) / 2; var fa = f(a); if (fa * f(b) >= 0) { throw new ArgumentException("f(a)とf(b)は異符号である必要があります。"); } for (int i = 0; i < loopLimit; i++) { var fmid = f(mid); var sign = fa * fmid; if (sign < 0) { b = mid; } else if (sign > 0) { a = mid; fa = fmid; } else { return mid; } mid = (a + b) / 2; if (Math.Abs(b - a) < eps) { break; } } return mid; } } } #endregion