LeetCode Weekly Contest 355 : 2791. Count Paths That Can Form a Palindrome in a Tree

難易度8出たの3年ぶり？
https://leetcode.com/contest/weekly-contest-355/problems/count-paths-that-can-form-a-palindrome-in-a-tree/

問題

木を成す無向グラフが与えられる。
各辺にはアルファベット1文字が設定されている。

このグラフのパスに対し、パス上の辺に設定された文字を、並べ替えながら連結した文字列が回文とできるのは何通りか。

解法

f(v) := 根頂点から点vに至るパス上の文字の登場頻度のパリティからなるbitmask

とすると、u→vからなるパス上の文字の登場頻度の偶奇はf(u) xor f(v)である。
f(u) xor f(v)のうち立ってるビットが1個以下なら回文にできるので、各f(v)に対し、あり得るf(u)のパターンを総当たりすればよい。

int mask[101010];
unordered_map<int,int> M;
vector<pair<int,int>> E[101010];
ll ret;
string S;
class Solution {
public:
	void dfs(int cur,int pre,int m) {
		mask[cur]=m;
		ret+=M[m]++;
		int j;
		FOR(j,26) ret+=M[m^(1<<j)];
		FORR(e,E[cur]) if(e.first!=pre) dfs(e.first,cur,mask[cur]^(1<<e.second));
	}

    long long countPalindromePaths(vector<int>& parent, string s) {
		S=s;
		int n=parent.size();
		int i;
		FOR(i,n) E[i].clear();
		FOR(i,n) if(i) {
			E[parent[i]].push_back({i,s[i]-'a'});
			E[i].push_back({parent[i],s[i]-'a'});
		}
		M.clear();
		ret=0;
		dfs(0,0,0);
		
		return ret;
        
    }
};

まとめ

知ってれば簡単だけど…map使ったら一度TLEしちゃった。