作者：FZANOTFOUND，MeltySnow_，coord_axis

文件头可参考以下代码

// 初音未来-纳西妲-芙宁娜第一可爱喵
#include <bits/stdc++.h>
using namespace std;

#define pb push_back 
#define eb emplace_back 
#define fi first
#define se second
#define ne " -> "
#define sep "======"
#define fastio ios::sync_with_stdio(false);cin.tie(0);
#define fill(a) iota(a.begin(), a.end(), 0)
#define all(a) a.begin(), a.end()
// 交互题记得注释
#define endl '\n'

typedef long long ll;
typedef long double db;
typedef pair<long long,long long> PLL;
typedef tuple<ll,ll,ll> TLLL;
//const ll inf =  0x3f3f3f3f3f3f;
const ll INF = (ll)2e18+9;
const ll MOD = 1000000007;
//const ll MOD = 998244353;
const db PI = 3.14159265358979323;

//io functions
inline void rd(ll &x){x=0;short f=1;char c=getchar();while((c<'0'||c>'9')&&c!='-') c=getchar();if(c=='-') f=-1,c=getchar();while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();x*=f;}  
inline ll read(){ll x=0;short f=1;char c=getchar();while((c<'0'||c>'9')&&c!='-') c=getchar();if(c=='-') f=-1,c=getchar();while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();x*=f;return x;}  
inline void pt(ll x){if(x<0) putchar('-'),x=-x;if(x>9) pt(x/10);putchar(x%10+'0');}
inline void print(ll x){pt(x), puts("");}
inline void printPLL(PLL x){pt(x.fi), putchar(' '), pt(x.se), putchar('\n');}
inline void printVec(vector<ll> &vec){for(const auto t:vec)pt(t),putchar(' ');puts("");}
inline void printMap(const map<ll, ll>& g) {for(const auto& [key, value]:g){cout<<"key: "<<key<<ne<<value<<" ";}puts("");}
inline void printVPLL(vector<PLL> &vec){puts(sep);for(const auto v:vec){printPLL(v);}puts(sep);}
inline void printVecMap(const map<ll, vector<ll>>& g) {for (const auto& [key, value] : g) { cout << "key: " << key << ne;for (const auto& v : value) {cout << v << " ";}cout << endl;}}

//fast pow
ll ksm(ll a, ll b){ll res = 1;while(b){if(b&1){res=(res*a)%MOD;}a=(a*a)%MOD;b>>=1;}return res;}

void solve(){
    
}

int main(){
    ll t = 1;
    //t = read();
    while(t--){
        solve();
    }
}

觉得长就对了，毕竟兼容了三个人的板子

1001小凯逛超市

这是一道完全背包板子题 [完全背包][https://oi-wiki.org/dp/knapsack/]

注意每个物品的体积都是 $1$
注意下面m是费用，V是体积，和题面意义相反（因为我总是把V当作体积（）

void solve() {
	ll n, m, V;
	cin >> n >> V >> m;
	vector<ll> a(1 + n);
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	vector<vector<ll>> dp(m + 1, vector<ll>(V + 1));
	dp[0][0] = 1;
	for (int i = 1; i <= n; i++) {
		ll cur = a[i];
		for (int j = 0; j <= m - cur; j++) {
			for (int k = 0; k  <= V - 1; k++) {
				dp[cur + j][k + 1] += dp[j][k];
				dp[cur + j][k + 1] %= mod;
			}
		}
	}
	ll ans = 0;
	for (int i = 0; i <= m; i++) ans += dp[i][V];
	cout << ans % mod << "\n";
}

1003 小凯去唱k

此做法能过可能是由于题目数据水了（

刚开始每个树的节点都是空的，操作一表示在节点 $x$ 添加数字 $y$ ，操作二表示:将节点 $x$ 的子树下的所有节点包含的数字凑成一个集合，查询该集合的子集的异或第 $k$ 小(除去 $0$ )

操作二其实是异或线性基的一个板子题（但是要用高斯消元法求线性基）

那么，这道题重要的观察是: 每个节点最多有 $30$ 个线性基(因为插入的数字$\le 10^9$)

我们试着从节点 $x$ 出发，一直向根节点前进，把路上经过的每一个节点的线性基末尾都添加上 $x$，再重新构造线性基。这里有个剪枝优化：如果节点 $u$ 重新构造前的线性基的大小，与重新构造后的线性基大小相同，则说明添加上的数字 $x$ 对它是没有贡献的，如果此时再往上走，都是做不出贡献的（因为 $u$ 的祖先节点所表示的子树必然包含 $u$ 的子树的线性基）。所以这个时候就直接停止向根节点前进。

void solve() {
    ll n, q;
    cin >> n >> q;
    vector<vector<ll>> g(n + 1);
    vector<vector<ll>> rg(n + 1);
    for (int i = 0; i < n - 1; i++) {
        ll u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    function<void(ll, ll)> pdfs = [&](ll u, ll f) {
        if (f != 0) rg[u].push_back(f);
        for (auto v : g[u]) {
            if (v == f) continue;
            pdfs(v, u);
        }
    };
    pdfs(1, 0);
    vector<vector<ll>> xxj(n + 1);
    function<void(ll, ll)> modify = [&](ll u, ll x) {
        if (xxj[u].size() >= 31) return;
        xxj[u].push_back(x);
        ll pres = xxj[u].size();
        ll k = 0;
        for (int i = 30; i >= 0; i--) {
            for (int j = k; j < pres; j++) {
                if (xxj[u][j] >> i & 1) {
                    swap(xxj[u][j], xxj[u][k]); break;
                }
            }
            if (!(xxj[u][k] >> i & 1)) continue;
            for (int j = 0; j < pres; j++) {
                if (j != k && (xxj[u][j] >> i & 1)) xxj[u][j] ^= xxj[u][k];
            }
            k++; if (k == pres) break;
        }
        xxj[u].resize(k);
        if (k != pres) return;
        for (auto v : rg[u]) {
            modify(v, x);
        }
    };
    while (q--) {
        ll op, x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            modify(x, y);
        }
        else {
            ll ans = 0;
            ll k = xxj[x].size();
            if (y >= (1 << k)) cout << -1 << "\n";
            else {
                for (int i = 0; i < k; i++) {
                    if ((y >> i) & 1) ans ^= xxj[x][k - i - 1];
                }
                cout << ans << "\n";
            }
        }
    }

}

1004 小凯爱数学

我们把余数分组，显然余数为 $r$ 和余数为 $m-r$ （$ 0 \leq r < m$）的数字可以组成 $m$ 的倍数。所以我们记录 $cnt[r]$ 为余数为 $ri$ 的数字个数。这就会变成一个模 $m$ 情况下的背包问题，问题就转化为，从这些余数中选若干个（每个余数r可以选 $0$ 到 $cnt[r]$ 次），使得它们的和模 $m$ 等于0。这里的子集是非空的，所以需要总方案数减去空集的情况。

然后，我们考虑动态规划， $dp[i][j]$ 表示前i种余数中，选取若干数，使得总和的余数是 $j$ 的方案数。这里可能需要将余数分组，每个余数r对应的数的数量是 $cnt[r]$ ，然后计算每个余数r的贡献，用生成函数来合并这些贡献。

每个余数 $r$ 对应的生成函数是 $(1+x^r{)}^k$，其中 $k$ 是该余数的出现次数。因为每个数可选可不选，所以生成函数是乘积的形式。生成函数的乘积在模m下的结果即为所有可能组合的余数分布。

vector<ll> multiply(const vector<ll>& a, const vector<ll>& b, int m) {
	vector<ll> res(m, 0);
	for (int i = 0; i < m; ++i) {
		if (a[i] == 0) continue;
		for (int j = 0; j < m; ++j) {
			if (b[j] == 0) continue;
			int k = (i + j) % m;
			res[k] = (res[k] + a[i] * b[j]) % MOD;
		}
	}
	return res;
}

vector<ll> pow_gf(int r, ll c, int m) {
	vector<ll> ini(m, 0);
	ini[0] = 1;
	ini[r % m] = (ini[r % m] + 1) % MOD;
	vector<ll> res(m, 0);
	res[0] = 1;
	while (c > 0) {
		if (c % 2 == 1) {
			res = multiply(res, ini, m);
		}
		ini = multiply(ini, ini, m);
		c /= 2;
	}
	return res;
}

void solve() {
	ll n, m;
	cin >> n >> m;
	vector<ll> cnt(m, 0);
	for (int r = 0; r < m; ++r) {
		if (r == 0) {
			cnt[r] = n / m;
		} else {
			if (r > n) {
				cnt[r] = 0;
			} else {
				cnt[r] = (n - r) / m + 1;
			}
		}
	}
	vector<ll> dp(m, 0);
	dp[0] = 1;
	for (int r = 0; r < m; ++r) {
		ll c = cnt[r];
		if (c == 0) continue;
		vector<ll> gf = pow_gf(r, c, m);
		vector<ll> new_dp(m, 0);
		for (int i = 0; i < m; ++i) {
			if (dp[i] == 0) continue;
			for (int j = 0; j < m; ++j) {
				if (gf[j] == 0) continue;
				int k = (i + j) % m;
				new_dp[k] = (new_dp[k] + dp[i] * gf[j]) % MOD;
			}
		}
		dp = new_dp;
	}
	ll ans = (dp[0] - 1 + MOD) % MOD;
	cout << ans << '\n';
}

1006小凯在长跑

由题意易得，最短路径肯定垂直于跑道。

对跑道上的每一点做法线不难发现，最短距离可以分 $-d\le y\le d$, $y>d$, $y<d$ 三部分。

即 $-d\le y\le d$ 部分最短路径为直接走到矩形区域上

其余部分沿着直径方向到达。

void solve(){
    ll d, r, x, y;
    cin>>d>>r>>x>>y;
    if(-d<=y&&y<=d){
        cout<<min(abs(-r-x), abs(r-x))<<'\n';
    }
    else if(y>d){
        cout<<fabs(sqrt(x*x+(y-d)*(y-d))-r)<<'\n';
    }
    else{
        cout<<fabs(sqrt(x*x+(y+d)*(y+d))-r)<<'\n';
    }
}

1007 小凯用git

纯暴力（没了)

我们需要维护的有提交节点的所有父节点，分支指向的节点，当前分支，总共有多少个点

commit 的时候新建节点，并把当前分支指向的节点添加进新建的节点的父节点组里。

brunch操作按题意删或添加即可，注意 brunch 要维护它指向了哪里

merge 可以纯暴力做，先获取 merge 节点的所有祖先节点，再获取当前分支指向的节点的所有祖先节点，按题意判断子集关系后更改。

checkout reset 按题意模拟

最后按题意打印当前状态

vector<string> split(const string &s) {
	vector<string> res;
	stringstream ss(s);
	string token;
	while (ss >> token) {
		res.push_back(token);
	}
	return res;
}

ll check(unordered_set<ll>& a, unordered_set<ll>& b) {
	for (int x : a) {
		if (b.find(x) == b.end()) {
			return 0;
		}
	}
	return 1;
}

class GIT{
    private:
    ll mxn;
	unordered_map<string, ll> branches;
	string curb;
	vector<vector<ll>> parents;
    unordered_set<ll> get(ll node) {
        unordered_set<ll> vis;
        stack<ll> s;
        s.push(node);
        while (!s.empty()) {
            ll n = s.top();
            s.pop();
            if (vis.count(n)) continue;
            vis.insert(n);
            for (ll p : parents[n]) {
                s.push(p);
            }
        }
        return vis;
    }
    public:
	GIT() {
		mxn = 1;
		branches["main"] = 1;
		curb = "main";
		parents.resize(2);
	}

    void commit(){
        ll curn = branches[curb];
        ll newn = mxn +1;
        if(newn>=parents.size()) parents.resize(newn+1);
        parents[newn].pb(curn);
        branches[curb] = newn;
        mxn = newn;
    }

    void delBrunch(string b){
        if (branches.count(b)) {
            branches.erase(b);
        }
    }

    void addBrunch(string newb){
        addBrunch(newb, branches[curb]);
    }

    void addBrunch(string newb, ll node){
	    branches[newb] = node;
    }

    void checkout(string b){
        curb = b;
    }

    void reset(){
        reset(branches[curb]);
    }

    void reset(ll node){
        branches[curb] = node;
    }

    void merge(string b){
        ll curn = branches[curb];
		ll mern = branches[b];
        unordered_set<ll> fcur = get(curn), fmer = get(mern);
        ll f1 = check(fcur, fmer), f2 = check(fmer, fcur);
        if(!f1&&!f2){
            ll newn = mxn +1;
            if(newn>=parents.size()) parents.resize(newn+1);
			parents[newn].push_back(curn);
			parents[newn].push_back(mern);
			branches[curb] = newn;
            mxn = newn;
        }
        else if(f1){
            branches[curb] = mern;
        }
    }

    void print(){
        vector<pair<string, ll>> ans;
        for (auto p : branches) {
            ans.pb(p);
        }
        sort(all(branches));
        cout<<branches.size()<<"\n";
        for (auto [b, n] : branches) {
            cout<<b<<" "<<n<<"\n";
        }
        cout<<mxn<<"\n";
        for (ll i = 1; i <= mxn; i++) {
            vector<ll> tans = parents[i];
            sort(tans.begin(), tans.end());
            cout<<tans.size();
            for (ll p : tans) {
                cout<<" "<< p;
            }
            cout<<"\n";
        }
    }
};

void solve() {
    ll n;cin>>n;cin.ignore();
    GIT git;
    for(ll i=1;i<=n;i++){
        string s;
        getline(cin, s);
        auto cmd = split(s);
        if(cmd[0] == "commit") git.commit();
        else if(cmd[0] == "branch"){
            if(cmd[1] == "-d"){
                git.delBrunch(cmd[2]);
            }
            else{
                if(cmd.size()==2){
                    git.addBrunch(cmd[1]);
                }
                else{
                    git.addBrunch(cmd[1], stoi(cmd[2]));
                }
            }
        }
        else if(cmd[0] == "merge") git.merge(cmd[1]);
        else if(cmd[0] == "checkout") git.checkout(cmd[1]);
        else if(cmd[0] == "reset"){
            if(cmd.size()==1) git.reset();
            else git.reset(stoi(cmd[1]));
        }
    }
}

1008 小凯想要MVP!

• 在一个数组中，如果一个数字出现了多次，那么必然能分别选择不同位置的这个数构成两个相同的子序列。

• 根据抽屉原理，当$n>m$时，必然有一个数出现了两次，那么肯定符合。

• 对于剩下的情况，暴力枚举所有可能的子序列长度，检查是否有两个不相交的子序列。对于每个从 $1$ 到 $\lfloor \frac{n}{2}\rfloor$ 的k，生成所有可能的 $k$ 元素的子集，并记录它们的和以及所包含的元素的位置。对于每个和，检查是否存在两个子集 $A$ 和 $B$ ，它们的和相等，并且 $A$ 和 $B$ 不相交。时间复杂度为$2^n$ ，不知道为什么能过的。

bool check(vector<int>& a) {
    int n = C.size();
    for (int k = 1; k <= n / 2; ++k) {
        unordered_map<int, vector<vector<bool>>> sumMap;
        vector<bool> used(n, false);
        vector<int> idx(k);
        for (int i = 0; i < k; ++i) idx[i] = i;
        while (1) {
            vector<bool> mask(n, false);
            int sum = 0;
            for (int i : idx) {
                sum += a[i];
                mask[i] = true;
            }
            bool found = false;
            if (sumMap.count(sum)) {
                for (const auto& prevMask : sumMap[sum]) {
                    bool conflict = false;
                    for (int i = 0; i < n; ++i) {
                        if (prevMask[i] && mask[i]) {
                            conflict = true;
                            break;
                        }
                    }
                    if (!conflict) {
                        found = true;
                        break;
                    }
                }
                if (found) return true;
            }
            sumMap[sum].pb(mask);
            int pos = k - 1;
            while (pos >= 0 && idx[pos] == n - k + pos) --pos;
            if (pos < 0) break;
            idx[pos]++;
            for (int i = pos + 1; i < k; ++i) idx[i] = idx[i - 1] + 1;
        }
    }
    return false;
}

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    unordered_set<int> s;
    for (int num : a) {
        if (s.count(num)) {
            cout << "YES" << "\n";
            return;
        }
        s.insert(num);
    }
    if (n > m) {
        cout << "YES" << "\n";
        return;
    }
    if (check(a)) {
        cout << "YES" << "\n";
    } else {
        cout << "NO" << "\n";
    }
}

1009 小凯取石子

提示1：如果Kc0正常玩，而且小凯是先手，那么小凯能否获胜？计算sg数。

提示2：(现在Kc0随机玩)如果此时Kc0的sg数是 $0$，那么他一定失败吗？(是的)

如果此时Kc0的sg数是 $1$，那么他获胜的概率是多少？

提示3：小凯要想办法让Kc0的sg数等于 $0$，这样他就一定能获胜了。

通过在纸上计算sg数，我们能够发现，sg数的分布(从 $0$ 开始)是 $01011010110101101\mathrm{0...}$

设此时有 $x$ 个石子，如果你观察力足够强大，你可以发现当 $x\%5==0or2$ 时，sg数为 $0$ ，否则为 $1$。或者，你也可以在最前面添加 $11$ 发现规律(是 $11010$ 序列的重复)。

第一轮是Kc0操作，为了方便像提示做法一样计算，我们可以假设Kc0取完 $1$ 个石子和取完 $4$ 个石子后，再计算答案。

如果小凯当前的sg数是 $1$，那么小凯包赢。

如果小凯当前的sg数是 $0$，那么，设此时剩余x个石子，如果 $x\%5==0$，那么你接下来必须取 $1$ 个石子。不然的话，你会发现Kc0不管怎么取，留给你的sg数还是 $0$

同理，如果 $x\%5==2$，那么你接下来必须取 $4$个石子。

那么接下来Kc0就有 $\frac{1}{2}$ 的概率将sg数为 $1$ 的石子个数留给小凯，所以每回合过后小凯会有 $\frac{1}{2}$ 概率有必赢的手段。

代码实现如下：

ll inv2;
void solve() {
    ll n = read();
    function<ll(ll)> check = [&](ll x) {
        if (x < 0) return 1LL;
        if (x == 0) return 0LL;
        if ((x+2)%5 == 2 || (x+2)%5 == 4) {
            ll res = (1-ksm(inv2,((x-1)/5+1))+MOD)%MOD;
            return res;
        }
        else {
            return 1LL;
        }
    };
    ll ans = (inv2*check(n-1)%MOD + inv2*check(n-4)%MOD)%MOD;
    print(ans);  
}

int main(){
    inv2 = ksm(2, MOD-2);
    ll t = 1;
    t = read();
    while(t--){
        solve();
    }
}

本题也可以打表观察后做（提供的打表代码由于精度问题最多 $200$ 个）

$1\sim 50$ 的答案如下

499122177 1 249561089 499122177 1 499122177 1 124780545 249561089 1 249561089 1 62390273 124780545 1 124780545 1 31195137 62390273 1 62390273 1 15597569 31195137 1 31195137 1 7798785 15597569 1 15597569 1 3899393 7798785 1 7798785 1 1949697 3899393 1 3899393 1 974849 1949697 1 1949697 1 487425 974849 1

不难发现 $n\%5=2$ 或 $n\%5=0$ 时小凯必胜

其余情况发现没有明显的循环，尝试是否和 $n$ 有关

令 $t=\lfloor \frac{n}{5}\rfloor$

（接下来的比较玄学, 手写成分数形式会好猜一点）

可以发现

$n=1$ 特判 Kc0 有$\frac{1}{2}$赢

$n\%5=1$ 时 Kc0 有 $\frac{1}{2^t}$的概率赢

$n\%5=4$ 时 Kc0 有 $\frac{1}{2^{t+1}}$的概率赢

$n\%5=3$ 时 Kc0 有 $\frac{1}{2^{t+2}}$的概率赢

于是就做完啦

打表代码

//fast pow
ll ksm(ll a, ll b){ll res = 1;while(b){if(b&1){res=(res*a)%MOD;}a=(a*a)%MOD;b>>=1;}return res;}

ll maxn = 200;
vector<ll> pre(maxn+1);
vector<db> ppp(maxn+1);
ll inv2 = ksm(2, MOD-2);
int main(){
    pre[1] = ksm(2, MOD-2);
    ppp[1] = 1.0/2;
    pre[2] = 1;
    ppp[2] = 1.0;
    pre[3] = 3*ksm(4, MOD-2)%MOD;
    ppp[3] = 3.0/4;
    pre[4] = ksm(2, MOD-2);
    ppp[4] = 1.0/2;
    pre[5] = 1;
    ppp[5] = 1.0;
    pre[6] = ksm(2, MOD-2);
    ppp[6] = 1.0/2;
    pre[7] = 1;
    ppp[7] = 1.0;
    pre[8] = 7 * ksm(8, MOD-2)%MOD;
    ppp[8] = 7.0/8;
    for(ll i=9;i<=maxn;i++){
        // i- 1
        ll use1 = ppp[i-1-1]>ppp[i-1-4]?i-1-1:i-1-4;
        ppp[i] += ppp[use1]/2.0;
        pre[i] = (pre[i] + inv2 * pre[use1]%MOD)%MOD;
        // i- 4
        ll use2 = ppp[i-4-1]>ppp[i-4-4]?i-4-1:i-4-4;
        ppp[i] += ppp[use2]/2.0;
        pre[i] = (pre[i] + inv2 * pre[use2]%MOD)%MOD;
    }
    printVec(pre);
    print(pre[103]);

}

1010 小凯做梦

$dis(i,j),dis(i,k),dis(j,k)$ 三个值对 $2$ 取模后的结果相等，等效于它们三个奇偶性相同。在树上，任意两点的路径都是唯一的，我们不妨设 $dis(i,j)=dis(i,k)+dis(j,k)$ 。在这个条件下，我们很容易发现，只有三个值均为偶数时，才满足奇偶性相同。所以现在，问题简化为统计所有$i,j,k$两两间距为偶数的三元组。

在树中，我们先选择一个根，每个节点 $u$ 的深度 $dep[u]$ 记为根到 $u$ 的长度 $mod$ $2$。那么，对于任意两个点 $u,v$，路径的长度为 $dep[u]$ $xor$ $dep[v]$。

然后，我们把边权转化为点权，开一个数组$node$，$node[u]=dep[u]$ $mod$ $2$，那么，$u$ 到 $v$ 的距离就是 $node[u]$ $xor$ $node[v]$。所以，只有当 $node[u]$ 和 $node[v]$ 相同时，它们的异或结果是 $0$ ，也就是距离是偶数。

那么现在，问题转化为：找出所有三元组 $(i,j,k)$ ，使得:

• $node[i]$ $xor$ $node[j]=0$；

• $node[i]$ $xor$ $node[k]=0$；

• $node[j]$ $xor$ $node[k]=0$。

那么，我们只需要统计树中 $node$ 为 $1$ 的节点数量 $n$ ，和 $node$ 为 $0$ 的节点数量 $m$（ $BFS$ 或者 $DFS$ ），答案即为 $n^3+m^3$。

void solve() {
    int n;
    cin >> n;
    vector<vector<pair<int, int>>> adj(n + 1);
    for (int i = 0; i < n - 1; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        int parity = w % 2;
        adj[u].emplace_back(v, parity);
        adj[v].emplace_back(u, parity);
    }

    vector<int> node(n + 1, -1);
    queue<int> q;
    q.push(1);
    node[1] = 0;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (const auto& p : adj[u]) {
            int v = p.first;
            int w_parity = p.second;
            if (node[v] == -1) {
                node[v] = (node[u] + w_parity) % 2;
                q.push(v);
            }
        }
    }

    ll cnt0 = 0, cnt1 = 0;
    for (int i = 1; i <= n; ++i) {
        if (node[i] == 0) {
            cnt0++;
        } else {
            cnt1++;
        }
    }
    ll ans = cnt0 * cnt0 * cnt0 + cnt1 * cnt1 * cnt1;
    cout << ans << '\n';
}

我们其实还可以通过树形dp，用在线的做法完成这道题。

存储每个节点为根的子树下面，距离为奇数的节点的个数，和距离为偶数的节点的个数。

我们假设$i,j,k$ 三者的最近公共祖先为 $u$ ，

那么当我们遍历到子树 $u$ 时，枚举每一个子树 $v$，将情况分为 $6$ 种：

1. 子树 $v$ 中取 $1$ 个偶数节点，子树 $u$ 中取 $2$ 个偶数节点

2. 子树 $v$ 中取 $2$ 个偶数节点，子树 $u$ 中取 $1$ 个偶数节点

3. 子树 $v$ 中取 $1$ 个奇数节点，子树 $u$ 中取 $2$ 个奇数节点

4. 子树 $v$ 中取 $2$ 个奇数节点，子树 $u$ 中取 $1$ 个奇数节点

5. 子树 $v$ 中取 $1$ 个偶数节点，子树 $u$ 中取 $1$ 个偶数节点 // 两个点重合了

6. 子树 $v$ 中取 $1$ 个奇数节点，子树 $u$ 中取 $1$ 个奇数节点 // 两个点重合了

每个情况，都对 $ans$ 做出 $6$ 倍的贡献。计算方式：若三点互不相同，则 $(i,j,k),(i,k,j),(j,i,k),(j,k,i),(k,i,j),(k,j,i)$

若三点中有两点相同，则$(i,i,j),(i,j,i),(j,i,i),(i,j,j),(j,i,j),(j,j,i)$
另外，还有一种特殊的情况，就是$i,j,k$都是同一个点的情况。这里我们只要每次dfs遍历到节点$u$的时候，给$ans$加 $1$ 即可。具体见代码。

void solve() {
    ll n;
    cin >> n;
    ll ans = 0;
    vector<vector<PII>> g(n+1);
    for (int i = 0; i < n-1; i++) {
        ll u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v,w%2});
        g[v].push_back({u,w%2});
    }
    vector<PII> dp(n+1); // odd, even
    function<void(ll,ll)> dfs = [&](ll u, ll f) {
        dp[u].second = 1;// 自身到自身的距离为0
        ans++; // i,j,k三个点都是u
        for (auto [v,w]: g[u]) {
            if (v == f) continue;
            dfs(v, u);
            ll curodd,cureven;
            if (w == 1) {
                curodd = dp[v].second; cureven = dp[v].first;
                ans += (cureven)*(dp[u].second*(dp[u].second-1)/2)*6 + (cureven)*dp[u].second*6 + ((cureven)*(cureven-1)/2)*dp[u].second*6 + (curodd)*dp[u].first*6 + curodd*(dp[u].first*(dp[u].first-1)/2)*6 + (curodd*(curodd-1)/2)*dp[u].first*6;
                dp[u].first += dp[v].second, dp[u].second += dp[v].first;
            }
            else {
                curodd = dp[v].first; cureven = dp[v].second;
                ans += (cureven)*(dp[u].second*(dp[u].second-1)/2)*6 + (cureven)*dp[u].second*6 + ((cureven)*(cureven-1)/2)*dp[u].second*6 + (curodd)*dp[u].first*6 + (curodd*(curodd-1)/2)*dp[u].first*6 + curodd*(dp[u].first*(dp[u].first-1)/2)*6;
                dp[u].first += dp[v].first, dp[u].second += dp[v].second;
            }
        }
    };
    dfs(1, 0);
    cout << ans <<endl;
}