這次比賽我依然是一如既往的唐詩...

后兩道根本不是我能碰的，所以就不總結了，前兩道題還是不錯的，我先整理 T2，再整理 T1，畢竟我覺得 T2 比較簡單。

我的統(tǒng)計方式似乎也是很為奇怪的。

因為今天晚上什么都不想干所以想盡可能寫的詳細一些。

T2

大概題意

給了一個 dfs 的方式

void dfs(int u) {
    vis[u] = true;
    for (int v = 1; v <= n; v++)
        if (g[u][v] == true && vis[v] == false)
            dfs(v), link(u, v);
}

這里的 g 就是我們常見的臨接矩陣， link 表示把 u, v 之間加一條邊。

容易發(fā)現(xiàn)，在 g 上最后我們會通過 link 連接出來一棵樹。

現(xiàn)在我們的問題是給出來你這個樹了，問你有幾種不同的圖的情況。

對于 1e9+7 取摸。

需要一個 O(nlogn)$ 的算法。

怎么做

我們首先根本不知道怎么直接去做這道題...

不知道怎么辦？可以去嘗試挖一挖性質(zhì)。

明顯我們的目的就是在這棵樹上加入一些邊，求出總數(shù)，并保證不影響正常的遍歷。

現(xiàn)在我們嘗試去尋找一些性質(zhì)，會發(fā)現(xiàn)簡單而且至關重要的性質(zhì)。

• 這些可能會被加入的邊相互之間并不會相互影響，所以我們可以使用乘法原理，一個這樣的邊有在或不在兩個狀態(tài)，假設我們知道這樣的邊有 \(miao\) 條，一共就會有 \(2^{miao}\) 種方案。

• 一個可能被加入的邊必須是從一個點連向她的祖先的，不然明顯這個點會影響我們的遍歷，注意我們統(tǒng)一采取從下到上的思考方式。

我們思考一下這個邊有什么具體的限制要求。

假設這個邊是 \(A\to B\) 的。

首先 \(B\) 是 \(A\) 的祖先，這一點我們前邊說過了。

我們現(xiàn)在需要考慮怎么加才能使得算法忽略掉這條邊。

因為我們的算法總是會走小的，所以只要我們保證 \(A\) 比這個 \(B\) 的兒子要大，我們就可以做到跳過這條邊正常向下了。

記下來。

• \(A>son[B]\)

注意這個 \(son\) 是 \(A\) 和 \(B\) 這一條鏈上的B的兒子，而不是通常意義上的那一堆兒子，特指這一個。

這樣還沒有完，看似我們已將問題討論完了，然而我們?nèi)匀徊盍艘粋€情況，玩意兒子和父親自導自演呢？我們注意到有一種情況，即使?jié)M足上邊的條件依然不能加，那就是他們是父子關系，中間是有直接連邊的。

這個需要特判一下的啦。

• \(A!=son[B]\)

接下來就都是實現(xiàn)的問題啦。

這個問題是每一個點到根節(jié)點的問題，我們使用一個數(shù)據(jù)結構維護每個點到根的這條鏈。

簡單說就是 dfs 的時候進入這個點的時候加入這個點的信息到數(shù)據(jù)結構里邊，遍歷完它的所有子樹后，退出時刪除它的信息。

我們以點的編號為下標建立一顆權值線段樹，這樣我們可以進行單點的修改和查詢維護的鏈上比一個編號小的點數(shù)。

為了比較簡潔，有藝術感的解決這個問題，我這個權值線段樹維護的是這個 \(son\)，也就是說每個點加進去并不代表自己，而是自己的父輩，自然我們特判一下是不是根節(jié)點，這樣實現(xiàn)起來比較符合我的審美。

這個問題就這么輕松解決了，個人評價綠題，都很套路。

那為什么 BaiBaiShaFeng 在這道題上只有 75pts 呢？

那是因為智慧無雙的白白殺瘋對我們統(tǒng)計的邊數(shù)直接取摸了，對冪次數(shù)取摸世界第一人，加上這個題數(shù)據(jù)非常的大的情況下真的有可能比 1e9+7 要大，導致有 25pts 的點直接就這么痛苦的消失了。

這啟示我們把歐拉定理寫在手上，錳綞茲季淂麼頑倚猈遐。

放一下我考場上美麗如藝術品的半壓行馬風。

代碼如下

#include <bits/stdc++.h>
#define int unsigned long long
using namespace std;
namespace DS{
	const int MN=1e6+116;
	struct MiaoMiaoTree{
		#define lc k<<1
		#define rc k<<1|1
		struct Node{
			int l, r, val;
		}tr[MN];
		void pushup(int k){
			tr[k].val=(tr[lc].val+tr[rc].val);
        }
		void build(int k, int l, int r){
			tr[k].l=l, tr[k].r=r;
			if(l==r){tr[k].val=0; return;}
			int mid=(tr[k].l+tr[k].r)>>1;
			build(lc,l,mid); build(rc,mid+1,r);
			pushup(k); return;
		}
		void update(int k, int pos, int val){
			if(tr[k].l==tr[k].r){
				tr[k].val+=val; return;
			}
			int mid=(tr[k].l+tr[k].r)>>1;
			if(pos<=mid) update(lc,pos,val);
			else update(rc,pos,val);
			pushup(k); return;
		}
		int query(int k, int l, int r){
			if(tr[k].l>=l&&tr[k].r<=r) return tr[k].val;
			int mid=(tr[k].l+tr[k].r)>>1,res=0;
			if(l<=mid) res+=query(lc,l,r);
			if(r>mid) res+=query(rc,l,r);
			return res;
		}
	};
}
namespace BaiBaiShaFeng{
	const int MN=1e6+116;
	const int mod=1e9+7;
	vector <int> G[MN];
	int n, ans=0;
	DS::MiaoMiaoTree tr;
	int quick_power(int a, int b, int mod){
		int res=1; a%=mod;
		while(b){
			if(b&1) res=(res*a)%mod;
			a=(a*a)%mod; b>>=1;}
		return res;
	}
	void dfs(int u, int father){
		if(u!=1){
			ans=(ans+tr.query(1,1,u-1));
		}
		if(u!=1) tr.update(1,u,1);
		for(auto v:G[u]){
			if(v==father) continue;
			dfs(v,u);
		}
		if(u!=1) tr.update(1,u,-1);
	}
	void solve(){
		cin>>n; tr.build(1,1,n);
		//cout<<"Miaop"<<'\n';
		for(int i=1,u,v; i<n; ++i){
			cin>>u>>v; G[u].emplace_back(v);
			G[v].emplace_back(u);
		}
		for(int i=1; i<=n; ++i) sort(G[i].begin(),G[i].end());
		dfs(1,1);
		cout<<quick_power(2,ans,mod)%mod<<'\n';
	}
}
signed main(){
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	BaiBaiShaFeng::solve(); return 0;
}