# LeetCode Find Duplicate Subtrees

LeetCode Find Duplicate Subtrees
Given a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of any one of them.
Two trees are duplicate if they have the same structure with same node values.
Example 1:

```        1
/ \
2   3
/   / \
4   2   4
/
4
```

The following are two duplicate subtrees:

```      2
/
4
```

and

```    4
```

Therefore, you need to return above trees' root in the form of a list.

```  1
/
2
```

``` 2
\
1```

```class Solution {
private:
string DFS(TreeNode* root, unordered_map<string, vector<TreeNode*>>& inorders) {
if (root == NULL)return "";
string left = DFS(root->left, inorders);
string right = DFS(root->right, inorders);
string cur = "(" + left + "," + to_string(root->val) + "," + right + ")";
inorders[cur].push_back(root);
return cur;
}
public:
vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
unordered_map<string, vector<TreeNode*>> inorders;
DFS(root, inorders);
vector<TreeNode*> ans;
for (auto &it : inorders) {
if (it.second.size() > 1)
ans.push_back(it.second[0]);
}
return ans;
}
};
```

# LeetCode Set Mismatch

LeetCode Set Mismatch
The set `S` originally contains numbers from 1 to `n`. But unfortunately, due to the data error, one of the numbers in the set got duplicated to another number in the set, which results in repetition of one number and loss of another number.
Given an array `nums` representing the data status of this set after the error. Your task is to firstly find the number occurs twice and then find the number that is missing. Return them in the form of an array.
Example 1:

```Input: nums = [1,2,2,4]
Output: [2,3]
```

Note:

1. The given array size will in the range [2, 10000].
2. The given array's numbers won't have any order.

```class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
vector<int> ans(2, 0);
unordered_set<int> hash;
int sum = 0, n = nums.size();
for (const auto& num : nums) {
if (hash.find(num) != hash.end())ans[0] = num;
hash.insert(num);
sum += num;
}
ans[1] = ans[0] - sum + n*(n + 1) / 2;
return ans;
}
};
```

```class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
vector<int> ans(2, 0);
for (int i = 0; i < nums.size(); ++i) {
int idx = nums[i] < 0 ? -nums[i] : nums[i];
if (nums[idx - 1] < 0) {
ans[0] = idx;
} else {
nums[idx - 1] = -nums[idx - 1];
}
}
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] > 0) {
ans[1] = i + 1;
break;
}
}
return ans;
}
};
```

# LeetCode Continuous Subarray Sum

LeetCode Continuous Subarray Sum
Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.
Example 1:

```Input: [23, 2, 4, 6, 7],  k=6
Output: True
Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.
```

Example 2:

```Input: [23, 2, 6, 4, 7],  k=6
Output: True
Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.
```

Note:

1. The length of the array won't exceed 10,000.
2. You may assume the sum of all the numbers is in the range of a signed 32-bit integer.

• [23,25,29,35,42]
• [5,1,5,5,0]

```class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
unordered_map<int, int> reminders;
reminders[0] = -1;
int accusum = 0;
for (int i = 0; i < nums.size(); ++i) {
accusum += nums[i];
if (k != 0)accusum %= k; // 注意k为0时，不能取模
if (reminders.find(accusum) != reminders.end()) {
if (i - reminders[accusum] >= 2)return true;
} else reminders[accusum] = i; // 注意必须是在else分支
}
return false;
}
};
```

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user and is able to see the 10 most recent tweets in the user's news feed. Your design should support the following methods:

1. postTweet(userId, tweetId): Compose a new tweet.
2. getNewsFeed(userId): Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
3. follow(followerId, followeeId): Follower follows a followee.
4. unfollow(followerId, followeeId): Follower unfollows a followee.

Example:

```Twitter twitter = new Twitter();
// User 1 posts a new tweet (id = 5).
// User 1's news feed should return a list with 1 tweet id -> [5].
// User 1 follows user 2.
// User 2 posts a new tweet (id = 6).
// User 1's news feed should return a list with 2 tweet ids -> [6, 5].
// Tweet id 6 should precede tweet id 5 because it is posted after tweet id 5.
// User 1 unfollows user 2.
// User 1's news feed should return a list with 1 tweet id -> [5],
// since user 1 is no longer following user 2.
```

```class Twitter {
private:
struct Tweet {
int userId;
int tweetId;
Tweet(int u, int t) :userId(u), tweetId(t) {};
};
vector<Tweet> Tweets;
unordered_map<int, unordered_set<int>> following;
public:
/** Initialize your data structure here. */
}
/** Compose a new tweet. */
void postTweet(int userId, int tweetId) {
Tweets.push_back({ userId,tweetId });
}
/** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */
vector<int> getNewsFeed(int userId) {
vector<int> ans;
for (int i = Tweets.size() - 1; i >= 0; --i) {
int &uid = Tweets[i].userId;
if (uid == userId || following[userId].find(uid) != following[userId].end()) {
ans.push_back(Tweets[i].tweetId);
if (ans.size() == 10)break;
}
}
return ans;
}
/** Follower follows a followee. If the operation is invalid, it should be a no-op. */
void follow(int followerId, int followeeId) {
following[followerId].insert(followeeId);
}
/** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
void unfollow(int followerId, int followeeId) {
following[followerId].erase(followeeId);
}
};
```

```class Twitter {
private:
int timestamp;
struct Tweet {
int tweetId;
int timestamp;
Tweet(int tid, int ts) :tweetId(tid), timestamp(ts) {};
bool operator<(const Tweet& t)const {
return timestamp < t.timestamp;
}
};
unordered_map<int, vector<Tweet>> Tweets;
unordered_map<int, unordered_set<int>> following;
public:
/** Initialize your data structure here. */
}
/** Compose a new tweet. */
void postTweet(int userId, int tweetId) {
Tweets[userId].push_back({ tweetId,timestamp++ });
}
/** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */
vector<int> getNewsFeed(int userId) {
priority_queue<Tweet> pq;
for (const auto& uid : following[userId]) {
for (const auto& t : Tweets[uid]) {
pq.push(t);
}
}
for (const auto& t : Tweets[userId]) {
pq.push(t);
}
vector<int> ans;
while (!pq.empty() && ans.size() < 10) {
ans.push_back(pq.top().tweetId);
pq.pop();
}
return ans;
}
/** Follower follows a followee. If the operation is invalid, it should be a no-op. */
void follow(int followerId, int followeeId) {
if (followerId != followeeId)following[followerId].insert(followeeId); // map中不考虑自己follow自己，因为getNewsFeed单独考虑了
}
/** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
void unfollow(int followerId, int followeeId) {
following[followerId].erase(followeeId);
}
};
```

# LeetCode Clone Graph

LeetCode Clone Graph
Clone an undirected graph. Each node in the graph contains a `label` and a list of its `neighbors`.

OJ's undirected graph serialization:Nodes are labeled uniquely.We use `#` as a separator for each node, and `,` as a separator for node label and each neighbor of the node.As an example, consider the serialized graph `{0,1,2#1,2#2,2}`.
The graph has a total of three nodes, and therefore contains three parts as separated by `#`.

1. First node is labeled as `0`. Connect node `0` to both nodes `1` and `2`.
2. Second node is labeled as `1`. Connect node `1` to node `2`.
3. Third node is labeled as `2`. Connect node `2` to node `2` (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

```       1
/ \
/   \
0 --- 2
/ \
\_/```

```class Solution {
private:
unordered_map<int, UndirectedGraphNode*> graph;
public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
if (node == NULL)return NULL;
if (graph.find(node->label) != graph.end())return graph[node->label];
UndirectedGraphNode *cur = new UndirectedGraphNode(node->label);
graph[cur->label] = cur;
for (auto& n : node->neighbors) {
cur->neighbors.push_back(cloneGraph(n));
}
return cur;
}
};
```

# LeetCode Design Excel Sum Formula

LeetCode Design Excel Sum Formula
Your task is to design the basic function of Excel and implement the function of sum formula. Specifically, you need to implement the following functions:
`Excel(int H, char W):` This is the constructor. The inputs represents the height and width of the Excel form. H is a positive integer, range from 1 to 26. It represents the height. W is a character range from 'A' to 'Z'. It represents that the width is the number of characters from 'A' to W. The Excel form content is represented by a height * width 2D integer array `C`, it should be initialized to zero. You should assume that the first row of `C` starts from 1, and the first column of `C` starts from 'A'.

`void Set(int row, char column, int val):` Change the value at `C(row, column)` to be val.

`int Get(int row, char column):` Return the value at `C(row, column)`.

`int Sum(int row, char column, List of Strings : numbers):` This function calculate and set the value at `C(row, column)`, where the value should be the sum of cells represented by `numbers`. This function return the sum result at `C(row, column)`. This sum formula should exist until this cell is overlapped by another value or another sum formula.
`numbers` is a list of strings that each string represent a cell or a range of cells. If the string represent a single cell, then it has the following format : `ColRow`. For example, "F7" represents the cell at (7, F).
If the string represent a range of cells, then it has the following format : `ColRow1:ColRow2`. The range will always be a rectangle, and ColRow1 represent the position of the top-left cell, and ColRow2 represents the position of the bottom-right cell.

Example 1:

```Excel(3,"C");
// construct a 3*3 2D array with all zero.
//   A B C
// 1 0 0 0
// 2 0 0 0
// 3 0 0 0
Set(1, "A", 2);
// set C(1,"A") to be 2.
//   A B C
// 1 2 0 0
// 2 0 0 0
// 3 0 0 0
Sum(3, "C", ["A1", "A1:B2"]);
// set C(3,"C") to be the sum of value at C(1,"A") and the values sum of the rectangle range whose top-left cell is C(1,"A") and bottom-right cell is C(2,"B"). Return 4.
//   A B C
// 1 2 0 0
// 2 0 0 0
// 3 0 0 4
Set(2, "B", 2);
// set C(2,"B") to be 2. Note C(3, "C") should also be changed.
//   A B C
// 1 2 0 0
// 2 0 2 0
// 3 0 0 6
```

Note:

1. You could assume that there won't be any circular sum reference. For example, A1 = sum(B1) and B1 = sum(A1).
2. The test cases are using double-quotes to represent a character.
3. Please remember to RESET your class variables declared in class Excel, as static/class variables are persisted across multiple test cases. Please see here for more details.

• Get(int row, char column)，获取坐标为(row,column)的cell的值
• Set(int row, char column, int val)，把坐标为(row,column)的值设置为val
• Sum(int row, char column, List of Strings : numbers)，numbers表示一系列求和公式，把公式计算结果填入坐标(row,column)中，并且当公式中的格子更新时，该公式计算出来的值也要更新。

Excel包含两个成员，二维矩阵matrix表示一个excel表格，hashmap formula的key为某个格子，value为该格子对应的求和公式。如果某个格子的值是实实在在的值，不是用公式计算出来的，则不在这个hashmap中。

• 对于get，如果坐标不在formula中，说明该格子是实实在在的值，直接返回matrix中的值。否则需要从formula中取出求和公式进行计算。
• 对于set，直接把matrix对应坐标设置为value就好，注意的是，因为set之后就变成了实实在在的值，所以要清空formula中该格子的公式（如果有的话）。
• 对于sum，计算字符串公式的值，把结果填入对应的格子，然后在formula中设置该格子的公式。

```class Excel {
private:
vector<vector<int>> matrix;
unordered_map<int, vector<string>> formula;
// 把坐标hash成一个int
int id(int r, char c) {
return r * 27 + c - 'A' + 1;
}
void parse(string& s, int& r, char& c) {
c = s[0];
r = stoi(s.substr(1));
}
int get_cell(string& s) {
int r;
char c;
parse(s, r, c);
return get(r, c);
}
int get_range(string& s) {
size_t pos = s.find(':');
string s1 = s.substr(0, pos), s2 = s.substr(pos + 1);
int r1, r2;
char c1, c2;
parse(s1, r1, c1);
parse(s2, r2, c2);
int ans = 0;
for (int i = r1; i <= r2; ++i) {
for (char c = c1; c <= c2; ++c) {
ans += get(i, c);
}
}
return ans;
}
int get_cells(vector<string>& strs) {
int ans = 0;
for (auto& s : strs) {
if (s.find(':') == string::npos)
ans += get_cell(s);
else
ans += get_range(s);
}
return ans;
}
public:
Excel(int H, char W) {
matrix.clear();
formula.clear();
for (int i = 0; i <= H; ++i) {
matrix.push_back(vector<int>(W - 'A' + 1, 0));
}
}
void set(int r, char c, int v) {
matrix[r] = v;
formula.erase(id(r, c)); // caution
}
int get(int r, char c) {
if (formula.find(id(r, c)) == formula.end())return matrix[r];
return get_cells(formula[id(r, c)]);
}
int sum(int r, char c, vector<string> strs) {
int ans = get_cells(strs);
matrix[r] = ans;
formula[id(r, c)] = strs;
return ans;
}
};
```

# LeetCode LRU Cache

LeetCode LRU Cache
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: `get` and `put`.
`get(key)` - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
`put(key, value)` - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
Could you do both operations in O(1) time complexity?
Example:

```LRUCache cache = new LRUCache( 2 /* capacity */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.put(4, 4);    // evicts key 1
cache.get(3);       // returns 3
cache.get(4);       // returns 4```

LRU的意思是Least Recently Used (LRU)，即把最近最久没访问的元素替换出去，是指时间上最久没访问的，而不是频率上访问最少的哦。

1. get(key)，从LRU中获取key对应的value，如果LRU中不存在key，则返回-1
2. put(key,value)，把key和对应的value插入到LRU中，如果LRU满，则要替换掉最近最久没访问的元素

put(key,value)。每当有新<key,value>进入时，如果key已经在cache中，则只需要更新key对应的value，同时，刚访问的元素下次很可能再次访问，所以需要把这个key提到链表的表头（为了不让这个key沉到表尾）。如果key不在cache中，但cache已满，则需要把链表尾部的key对应的数据在cache中删掉，同时也需要在链表中删掉这个尾节点；如果cache不满，则把新key插入到链表表头，同时把<key,value>插入到cache中，且key在链表中的位置是list.begin()。
get(key)。如果key不在cache中，直接返回-1。如果key在cache中，直接从cache中得到对应的value，同时根据迭代器，把key提到链表表头。

```class LRUCache {
private:
unordered_map<int, pair<int, list<int>::iterator>> cache;
list<int> used;
int _capacity;
// 把it节点**剪切**到表头
int key = *it;
used.erase(it);
used.push_front(key);
cache[key].second = used.begin();
}
public:
LRUCache(int capacity):_capacity(capacity) {
}
int get(int key) {
if (cache.find(key) == cache.end())return -1;
int value = cache[key].first;
return value;
}
void put(int key, int value) {
if (cache.find(key) != cache.end()) {
cache[key].first = value;
}
else {
if (used.size() == _capacity) {
cache.erase(used.back());
used.pop_back();
}
used.push_front(key);
cache[key] = { value,used.begin() };
}
}
};
```

``````头 --> 节 --> 节 --> 节 --> 尾

```class LRUCache {
private:
struct Node {
int key, value;
Node *pre, *next;
Node(int k, int v) :key(k), value(v), pre(NULL), next(NULL) {};
};
unordered_map<int, Node*> cache;
int _capacity;
// 从原链表中删除节点node（摘下）
void removeFromList(Node *node) {
node->pre->next = node->next;
node->next->pre = node->pre;
}
// 把节点node放到“表头”（安放）
}
// 删除“尾节点”
void removeTail() {
Node *target = tail->pre;
target->pre->next = target->next;
target->next->pre = target->pre;
delete target;
}
public:
LRUCache(int capacity) :_capacity(capacity) {
head = new Node(0, 0); // 辅助头结点
tail = new Node(0, 0); // 辅助尾节点
}
int get(int key) {
if (cache.find(key) == cache.end())return -1;
int value = cache[key]->value;
removeFromList(cache[key]);
return value;
}
void put(int key, int value) {
if (cache.find(key) != cache.end()) {
cache[key]->value = value;
removeFromList(cache[key]);
}
else {
if (cache.size() == _capacity) {
cache.erase(tail->pre->key);
removeTail();
}
Node *node = new Node(key, value);
cache[key] = node;
}
}
};
```

# LeetCode Lowest Common Ancestor of a Binary Tree

LeetCode Lowest Common Ancestor of a Binary Tree
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

```        _______3______
/              \
___5__          ___1__
/      \        /      \
6      _2       0       8
/  \
7   4
```

For example, the lowest common ancestor (LCA) of nodes `5` and `1` is `3`. Another example is LCA of nodes `5` and `4` is `5`, since a node can be a descendant of itself according to the LCA definition.

```struct MyNode {
TreeNode* node;
int par;
MyNode(TreeNode* n_, int p_) :node(n_), par(p_) {};
};
```

```class Solution {
private:
struct MyNode {
TreeNode* node;
int par;
MyNode(TreeNode* n_, int p_) :node(n_), par(p_) {};
};
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
vector<MyNode> nodes;
int i = 0, j = 0;
queue<MyNode> tree;
tree.push({ root,-1 });
while (!tree.empty()) {
MyNode cur = tree.front();
tree.pop();
if (cur.node == NULL) continue;
if (cur.node == p)i = nodes.size();
if (cur.node == q)j = nodes.size();
tree.push({ cur.node->left,nodes.size() });
tree.push({ cur.node->right,nodes.size() });
nodes.push_back(cur);
}
if (i == j)return nodes[i].node;
unordered_set<int> path1;
while (i != -1) {
path1.insert(i);
i = nodes[i].par;
}
while (j != -1) {
if (path1.find(j) != path1.end()) {
return nodes[j].node;
}
j = nodes[j].par;
}
return NULL;
}
};
```

```class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == NULL || root == p || root == q)return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left != NULL&&right != NULL)return root;
return left != NULL ? left : right;
}
};
```

# LeetCode Longest Uncommon Subsequence II

LeetCode Longest Uncommon Subsequence II
Given a list of strings, you need to find the longest uncommon subsequence among them. The longest uncommon subsequence is defined as the longest subsequence of one of these strings and this subsequence should not be any subsequence of the other strings.
A subsequence is a sequence that can be derived from one sequence by deleting some characters without changing the order of the remaining elements. Trivially, any string is a subsequence of itself and an empty string is a subsequence of any string.
The input will be a list of strings, and the output needs to be the length of the longest uncommon subsequence. If the longest uncommon subsequence doesn't exist, return -1.
Example 1:

```Input: "aba", "cdc", "eae"
Output: 3
```

Note:

1. All the given strings' lengths will not exceed 10.
2. The length of the given list will be in the range of [2, 50].

```class Solution {
private:
// 判断child是否是par的子序列
bool isSubSeq(const string& par, const string& child) {
int i = 0, j = 0, m = par.size(), n = child.size();
while (i < m&&j < n) {
if (par[i] == child[j])++j;
++i;
}
return j == n;
}
public:
int findLUSlength(vector<string>& strs) {
unordered_map<string, int> hash;
for (const auto& s : strs)++hash[s];
sort(strs.begin(), strs.end(), [](const string& s1, const string& s2) {return s1.size() > s2.size(); });
for (int i = 0; i < strs.size(); ++i) {
if (hash[strs[i]] > 1)continue;
bool isSub = false;
for (int j = i - 1; j >= 0; --j) {
if (isSubSeq(strs[j], strs[i])) {
isSub = true;
break;
}
}
if (!isSub)return strs[i].size();
}
return -1;
}
};
```

# LeetCode Valid Triangle Number

LeetCode Valid Triangle Number
Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.
Example 1:

```Input: [2,2,3,4]
Output: 3
Explanation:
Valid combinations are:
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3
```

Note:

1. The length of the given array won't exceed 1000.
2. The integers in the given array are in the range of [0, 1000].

```class Solution {
private:
void dfs(int &ans, vector<int>& nums, vector<int>& cand, int idx) {
if (cand.size() == 3) {
int &a = cand[0], &b = cand[1], &c = cand[2];
if (a + b > c&&a + c > b&&b + c > a) {
++ans;
//cout << a << "\t" << b << "\t" << c << endl;
}
return;
}
for (int i = idx; i < nums.size(); ++i) {
if (cand.size() == 2 && cand[0] + cand[1] <= nums[i])return;
cand.push_back(nums[i]);
dfs(ans, nums, cand, i + 1);
cand.pop_back();
}
}
public:
int triangleNumber(vector<int>& nums) {
int ans = 0;
vector<int> cand;
sort(nums.begin(), nums.end());
dfs(ans, nums, cand, 0);
return ans;
}
};
```

```class Solution {
private:
void dfs(int& ans, vector<int>& count, vector<int>& nums, vector<int>& cand, int idx) {
if (cand.size() == 3) {
int &a = cand[0], &b = cand[1], &c = cand[2];
if (a + b > c&&a + c > b&&b + c > a) {
ans += count[a] * count[b] * count; // 三边各异
//cout << a << "\t" << b << "\t" << c << endl;
}
return;
}
for (int i = idx; i < nums.size(); ++i) {
if (cand.size() == 2 && cand[0] + cand[1] <= nums[i])return;
cand.push_back(nums[i]);
dfs(ans, count, nums, cand, i + 1);
cand.pop_back();
}
}
public:
int triangleNumber(vector<int>& nums) {
vector<int> mii(1001, 0);
for (const auto& i : nums)++mii[i]; // hash
vector<int> distinct;
for (int i = 1; i < 1001; ++i) {
if (mii[i] > 0)distinct.push_back(i);
}
int ans = 0;
vector<int> cand;
dfs(ans, mii, distinct, cand, 0); // 三边互不相同
int n = distinct.size();
for (int i = 0; i < n; ++i) {
if (mii[distinct[i]] >= 3) { // 三边相同
int &d = mii[distinct[i]];
ans += (d*(d - 1)*(d - 2)) / 6;
}
for (int j = i + 1; j < n; ++j) {
if (mii[distinct[i]] >= 2) { // 两条边一样
int &a = distinct[i], &b = distinct[i], &c = distinct[j];
if (a + b > c&&a + c > b&&b + c > a) {
ans += (mii[a] * (mii[a] - 1) / 2)*mii;
}
}
if (mii[distinct[j]] >= 2) { // 两条边一样
int &a = distinct[i], &b = distinct[j], &c = distinct[j];
if (a + b > c&&a + c > b&&b + c > a) {
ans += (mii[b] * (mii[b] - 1) / 2)*mii[a];
}
}
}
}
return ans;
}
};
```